УП_САОД_2003

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

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

В процессе своей работы алгоритм строит множество 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

Рисунок 53. Алгоритм Дейкстры

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

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

Содержание