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

Нахождение расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Дано: ориентированный граф <V,E> с выделенным источником s € V, матрица весов дуг A[u,v], u,v € V (все веса неотрицательны). Результат: расстояние от источника до всех вершин графа D[v]=d(s,v), v € V.

begin

for v € V do D[v]:=A[s,v];

D[s]:=0;

T:=V \ {s};

while T<> Ø do begin

u:=произвольная вершина r € T, такая что D[r]=min{D[p]:p € T};

T:=T \ {u};

for v € T do D[v]:=min(D[v], D[u]+A[u,v]}

end

end