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

Пуст дан ориентированный граф G=< V, E>, s — вершина-источ­ник; матрица смежности А (Array[1..N, 1..N] Of Integer); для любых u, v V вес дуги неотрицательный (A[u, v] 0). Резуль­тат — массив кратчайших расстояний D.

В данном алгоритме формируется множество вершин Т, для которых еще не вычислена оценка расстояние и, во-вторых, минимальное значение в D по множеству вершин, принадлежащих Т, считается окончательной оценкой для вер­шины, на которой достигается этот минимум. С точки зрения здравого смысла этот факт достаточно очевиден. Другой «за­ход» в эту вершину возможен по пути, содержащему большее количество дуг, а так как веса неотрицательны, то и оценка пути будет больше.

Пример. Дан граф и его матрица смежности (см. рис. 5).

 

рис.5

В таблице 2 приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества T, и улучшение оценки до оставшихся вершин (3, 4, 5, 6) ищется не по всем вершинам, а только от второй.

Таблица 2

№ итерации	D[1]	D[2]	D[3]	D[4]	D[5]	D[6]	T
							[2, 3, 4, 5, 6]
							[3, 4, 5.6]
							[3, 4, 5]
							[4, 5]
							[5]

 

Procedure Dist; (*A, D, s, N - глобальные величины. *}

Var i, u; Integer;

T: Set Of 1..N;

Begin

For i: =1 To N Do D[i]: =A[s, i];

D[s]: =0;

T: -[l..N]-[s];

While T< > [] Do

Begin u: =< то значение 1, при котором достигается

min(D[l])>;

T: =T-[u];

For i: =1 To N Do

If i In T Then D[i]: =min (D[i], D[u]+A[u, i}); End;

End;

Время работы алгоритма t^O(N2).