Алгоритмы на графах



бет1/4
Дата16.11.2022
өлшемі0,92 Mb.
#50601
  1   2   3   4

Алгоритмы на графах


Алгоритм

Объект работы

Действие

Сложность

Доп. память

Полезн.

Матрица

Список

Поиск в ширину

Невзвеш-й граф

Поиск кратчайшего расстояния от одной вершины до всех остальных, определение количества компонент связности, определение двудольности графа

O(N2)

O(M)

O(N)

10

Поиск в глубину

Невзвеш-й граф

Определение количества компонент связности, построение дерева поиска в глубину, поиск точек сочленения и мостов, определение двудольности графа

O(N2)

O(M)

O(N)

8

Алгоритм Дейкстры

Взвеш-й граф без рёбер отрицат-го веса

Поиск кратчайшего расстояния от одной вершины до всех остальных

O(N2)

O(N2),

O(N)

10

Алгоритм Форда-Беллмана

Взвешенный граф

Поиск кратчайшего расстояния от одной вершины до всех остальных

O(N3)

O(MN)

O(N)

5

Алгоритм Флойда

Взвешенный граф

Поиск кратчайшего расстояния между каждой парой вершин

O(N3)

O(N2)

8

Основные алгоритмы

  • Нахождение кратчайших путей из одного источника: алгоритм Дейкстры.
  • Построение минимального остова графа: алгоритм Крускала.
  • Задача о лабиринте и поиск в глубину на неориентированном графе.

Алгоритм Дейкстры

Алгоритм Дейкстры

Алгоритм Дейкстры

  • Э́дсгер Ви́бе Де́йкстра (Edsger Wybe Dijkstra [ˈɛtsxər ˈʋibə ˈdɛikstra]) (11 мая 1930, Роттердам, Нидерланды — 6 августа 2002) — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии.

Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э.Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных.

Алгоритм работает только для графов без рёбер отрицательного веса.

Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Формулировка задачи

Дан взвешенный ориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины а до всех остальных вершин этого графа

Граф называется взвешенным или нагруженным, если каждому ребру поставлено в соответствии некоторое число w (вес).

Алгоритм


Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до  а. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Метка самой вершины  а  полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.


Достарыңызбен бөлісу:
  1   2   3   4




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет