Алгоритм Дейкстры
Более эффективным алгоритмом для решения данной задачи является алгоритм Дейкстры , применяемый в том случае, если веса всех дуг неотрицательны [Липский,1988]. Исходная информация и результаты работы аналогичны предыдущему алгоритму.
For v I V do D [ v ]:= A [ s , v ];
D[s]:=0; T:=V\{s};
While T?0 do
begin
u:=Произвольная вершина rIT , такая, что D[ r ]= min {D[p]:pIT};
T:=T\{u};
For vIT do D[v]:=min(D[v],D[v]+A[u,v])
end
Механизм работы алгоритма Дейкстры представлен на следующем рисунке [ Бурковский , Холопкина , Райхель , Кравец,1996]:
