вершину с номером
вершину с номером t в Stack>;v:=t;
while v<>s do begin
u:=<номер вершины, для которой D[v]=D[u]+A[u,v]>;
<занести вершину с номером v в Stack>;
v:=u;
end;
end;
Итак, путь при известном D находить мы умеем. Осталось научиться определять значения кратчайших путей, то есть элементы массива D. Идея всех известных алгоритмов заключается в следующем. По данной матрице весов A вычисляются первоначальные верхние оценки. А затем пытаются их улучшить до тех пор, пока это возможно. Поиск улучшения, например для D[v], заключается в нахождении вершин u, таких, что D[u]+A[u,v]<D[v]. Если такая вершина u есть, то значение D[v] можно заменить на D[u]+A[u,v].
3.6.2. Алгоритм Дейкстры
Дано. Ориентированный граф G=<V,E>, s - вершина источник;
матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v?V вес дуги неотрицательный (A[u,v]?0).Результат. Массив кратчайших расстояний - D.
В данном алгоритме формируется множество вершин T,
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
