2014-02-09
3047
Нахождение кратчайшего пути
Задача нахождения кратчайших путей на графах; алгоритм Флойда; алгоритм Дейкстры
Здесь рассматриваются алгоритмы нахождения путей в ориентированном графе. Эти алгоритмы работают на ориентированном графе, у которого все дуги имеют неотрицательные метки (стоимости дуг). Задача алгоритмов состоит в нахождении кратчайших путей между вершинами графа. Длина пути здесь определяется как сумма меток (длин) дуг, составляющих путь.
Этот алгоритм находит в графе кратчайший путь из заданной вершины, определенной как источник, во все остальные вершины.
В процессе своей работы алгоритм строит множество 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 2), где n – количество вершин графа.
