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

Нахождение кратчайшего пути

Задача нахождения кратчайших путей на графах; алгоритм Флойда; алгоритм Дейкстры

 

 

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

 

 

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

В процессе своей работы алгоритм строит множество S вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. При этом используется массив D, в который записываются длины кратчайших путей для каждой вершины. Когда множество S будет содержать все вершины графа, тогда массив D будет содержать длины кратчайших путей от источника к каждой вершине.

Помимо указанных массивов, в алгоритме Дейкстры используется матрица длин C, где элемент C[i, j] – метка (длина) дуги (i, j), если дуги нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины дуг. Фактически, матрица C представляет собой матрицу смежности, в которой все нулевые элементы заменены на бесконечность.

Для определения самого кратчайшего пути (то есть последовательности вершин) необходимо ввести еще один массив P вершин, где P[v] содержит вершину, непосредственно предшествующую вершине v в кратчайшем пути.

 

 

procedure Dijkstra;

begin

S := источник;

for i := 2 to n do begin

D[i] := C[источник, i];

P[i] := источник;

end;

for i := 1 to n-1 do begin

выбор из множества V\S такой вершины w,

что значение D[w] минимально;

добавить w к множеству S;

for каждая вершина v из множества V\S do begin

D[v] := min(D[v], D[w] + C[w, v]);

if D[w] + C[w, v]< D[v] then P[v] := w;

end;

end;

end

 

 

Листинг 5.11 – Алгоритм Дейкстры

 

 

Листинг 5.12 – Алгоритм Дейкстры

 

Рисунок 5.11 – Работа алгоритма Дейкстры

 

После выполнения алгоритма кратчайший путь к каждой вершине можно найти с помощью обратного прохождения по предшествующим вершинам массива P, начиная от конечной вершины к источнику.

Время выполнения этого алгоритма, если для представления графа используется матрица смежности, имеет порядок O(n²), где n – количество вершин графа.