Алгоритм Дийкстры
Пуст дан ориентированный граф G=< V, E>, s — вершина-источник; матрица смежности А (Array[1..N, 1..N] Of Integer); для любых u, v В данном алгоритме формируется множество вершин Т, для которых еще не вычислена оценка расстояние и, во-вторых, минимальное значение в D по множеству вершин, принадлежащих Т, считается окончательной оценкой для вершины, на которой достигается этот минимум. С точки зрения здравого смысла этот факт достаточно очевиден. Другой «заход» в эту вершину возможен по пути, содержащему большее количество дуг, а так как веса неотрицательны, то и оценка пути будет больше. Пример. Дан граф и его матрица смежности (см. рис. 5).
В таблице 2 приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества T, и улучшение оценки до оставшихся вершин (3, 4, 5, 6) ищется не по всем вершинам, а только от второй. Таблица 2
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).
|
V вес дуги неотрицательный (A[u, v] 
0). Результат — массив кратчайших расстояний D.
рис.5
