38. Метод Дейкстры нахождения расстояний от вершины - “источника” до остальных вершин. Временная сложность алгоритма. Алгоритм восстановления кратчайшего пути по известным расстояниям. Временная сложность алгоритма

 

Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF(Open Shortest Path First) для устранения кольцевых маршрутов.

 

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

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Новосибирской области. Некоторые дороги односторонние. Найти кратчайшие пути от Новосибирска до каждого города области (если двигаться можно только по дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Неформальное объяснение

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

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

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

 

Алгоритм

Обозначения

§     V — множество вершин графа

§     E — множество ребер графа

§     w[ij] — вес (длина) ребра ij

§     a — вершина, расстояния от которой ищутся

§     U — множество посещенных вершин

§     d[u] — по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u

§     p[u] — по окончании работы алгоритма содержит кратчайший путь из a в u

Псевдокод

Присвоим d[a] \gets 0,\ p[a] \gets a

Для всех u \in V отличных от a

присвоим d[u] \gets \infty

Пока \exists v \notin U

Пусть v \notin U — вершина с минимальным d[v]

Для всех u \notin U таких, что vu \in E

если d[u] > d[v] + w[vu] то

изменим d[u] \gets d[v] + w [vu]

изменим p[u] \gets p[v], u

 

Описание

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.

В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (большим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин с флагом 0 d[i] = \infty. Последний случай возможен тогда и только тогда, когда граф G не связан.

 

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.

В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.

 

Пусть мы знаем кратчайшие расстояния до всех вершин. Как найти кратчайший путь до конкретной вершины? Рассмотрим эту вершину (обозначим ее V). Пусть длина пути до нее L. Эта вершина является последней в пути к V. Найдем какую-нибудь вершину, которая соединена с V, и расстояние до которой равно L-1. Тогда эта вершина является предпоследней в пути (если таких вершин несколько, значит, существует несколько кратчайших путей и можно выбрать любую из этих вершин). Далее найдем вершину, которая соединена с предпоследней и расстояние до которой равно L-2. Она является пред-предпоследней. Продолжая этот процесс, мы можем "раскрутить" весь путь задом наперед. Осталось только запомнить его в массиве и вывести в правильном порядке.