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

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

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

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

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

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

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

Алгоритм:

procedure Dijkstra; begin

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

for i := 2 to n do begin

158

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;

Итерация

начало

1

2

3

4

Массив P: Кратчайши

s	w	D[2]	D[3]	D[4]	D[5]
{1}	-	10	oo	30	100
{1, 2}	2	10	60	30	100
{1, 2, 4}	4	10	50	30	90
{1, 2, 4, 3}	3	10	50	30	60
{1, 2, 4, 3,5}	5	10	50	30	60
[XI 1 1	4 1 1		1 3

путь из 1 в 5: {1, 4, 3, 5}

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

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

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