Алгоритм Дейкстры поиска кратчайшего пути

Алгоритм Дейкстры находит кратчайший (т.е. с минимальной суммой длин дуг) путь от заданного узла s к узлу t во взвешенном орграфе. В алгоритме 3.3 мы приводим его простейшую запись, нс самую эффективную и достаточно длинную, но наиболее наглядную и понятную, по нашему мнению^[1]. В этой записи узлы орграфа перенумерованы, а сам орграф задан матрицей длин дуг С: array [l.n, l. n] of real, где C[i, i]=0, С [ i, j ]—некоторое неотрицательное число, если есть дуга из узла с номером i в узел с номером j и С [ i, i ] =°°, есть нет дуги из узла с номером i в узел с номером j. В результате работы алгоритма заполняются два массива: вектор Т: array [l.n] of real и H: array [ 1. n] of 0. n, где n — число узлов в орграфе. При этом если узел v лежит на кратчайшем пути от узла s к узлу t, то Т [v] — длина кратчайшего пути от s к v, а Н [ v ] — узел, непосредственно предшествующий узлу v на кратчайшем пути от узла s к узлу t. Такой прием позволяет компактно записать найденный путь. Кроме того, в процессе работы алгоритм использует временный массив пометок X: array [l.n] of bool.

Алгоритм 33. Поиск кратчайшего пути

Proc Dijkstra (С: array [l.n, l. n] of real, // длины дуг Т: array [l.n] of real, // длины путей .

H: array [l.n] of 0. n) // пред, узел. for v from 1 to n do T[v] := °° // кратчайший путь неизвестен X[v] := false // все вершины не отмечены end for.

H[s] := 0 // узлу s ничего не предшествует T[s] := 0 // кратчайший путь от s к s имеет длину О X[s] := true // и он известен v := s // текущая вершина while v*t do // обновление пометок for u from 1 to n do.

if C [v, u] T[v]+C[v, u] then.

T[u] := T[v]+C[v, u] // найден более.

// короткий путь из $s$ в $u$ через $v$ H[u] := v // запоминаем его.

end if.

end if.

end for.

// поиск конца кратчайшего пути m := v: =0.

for u from 1 to n do.

if —iX [ u ] & T[u] < m then.

// вершина v заканчивает // кратчайший путь из s.

v := u; m := T[u].

end if.

end for.

if v=0 then.

stop // нет пути из s в t.

end if.

X[v] := true // найден кратчайший путь из s в v.

end while end proc.

Заметим, что для применимости алгоритма Дейкстры достаточно, чтобы длины дуг были неотрицательны. Если же допускаются отрицательные длины дуг, то алгоритм Дейкстры может оказаться неприменимым.

Например, в графе с тремя узлами s, t и и, если С [ s, t ] =2, С [ s, u ] =3 и С[u, t]=-2, алгоритм 3.3 не найдет кратчайшего пути длиной 1 и выдаст путь длины 2.

Условие неотрицательности длин дуг является достаточным для корректной работы алгоритма Дейкстры, но не является необходимым. Например, в графе с тремя узлами s, t и и, если C[s, t]=2, C[s, u] =-2 и С [ u, t ] =3, алгоритм 3.3 найдет кратчайший путь длиной 1, хотя в графе присутствуют дуги отрицательной длины.

Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла while, в качестве v используется узел, для которого известен кратчайший путь из узла s. Другими словами, если X [ v] = true, то Т [v] = d (s, v), и все вершины на пути из узла s в узел v, определяемом вектором н, обладают тем же свойством, г. е.

Действительно (по индукции), первый раз в качестве v используется узел s, для которого кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т [u] =d (s, и) для всех ранее помеченных узлов и. Рассмотрим вновь помеченный узел v, который выбран из условия Т [v] = min{ T[u] | ->X[u] }. Заметим, что если известен путь, проходящий через помеченные вершины, то гем самым известен кратчайший путь. Допустим (от противного), что Т [v] >d (s, v), т. е. найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую чтоiX [w]. Имеем: T[w] = d (s, w) < T [v], что противоречит выбору вершины v и тем самым доказывает корректность алгоритма 3.3.

В изложенной версии алгоритма нетрудно показать, что оценка трудоемкости в худшем случае составляет 0(п²). Действительно, цикл while выполняется не более п раз, поскольку при каждом выполнении одна вершина отмечается, и повторно вершины не отмечаются. В теле этого цикла вложены два последовательных цикла, каждый из которых повторяется п раз. Однако можно заметить, что во внутренних циклах совершается лишняя работа: при поиске нового узла v, который завершает наикратчайший из построенных кратчайших путей, совершенно излишне проверять «далекие» узлы — они не могут оказаться искомым узлом v. Известно, что, тщательно подбирая структуры данных для хранения информации, можно снизить оценку трудоемкости алгоритма Дейкстры до 0(п log п) в худшем случае^[2].

Эдсгер Вибе Дейкстра (нидерл. Edsger Wybe Dijkstra), 1930— 2002 — выдающийся нидерландский ученый, идеи которого оказали огромное влияние на развитие программирования.

Занимался работами в области применения математической логики при разработке компьютерных программ, разработал язык программирования Алгол. Один из авторов концепции структурного программирования, автор ряда классических книг в этой области. В 1972 г. Дейкстра был удостоен премии Тьюринга.

«Вопрос «умеет ли компьютер думать» имеет не больше смысла, чем вопрос «умеет ли подводная лодка плавать ««.

• [1] Новиков Ф. А. Дискретная математика.
• [2] Романовский И. В. Дискретный анализ: учеб, пособие для студентов, специализирующихся по прикладной математике и информатике. СПб.: Невский Диалект, БХВ-Петербург, 2003.