Алгоритм нахождения расстояния от источника до всех остальных вершин в ориентированном графе с неотрицательными весами ребер

Исходные данные: G=<V, E > - ориентированный, связный, конечный граф c неотрицательными весами ребер.

v₀ - источник, v₀V.

- матрица весов ребер.

Результат: расстояния от источника до всех вершин графа

D[v]=d(v₀,v), vV.

Метод. Строим такое подмножество S множества вершин графа, , что кратчайший путь из источника в каждую вершину целиком лежит в S.

S:={v₀};

D[v]:=c(v₀,v); D[v₀]:=0;

while VS DO

begin

выбрать вершину uV\S,

для которой ;

;

для всех vV\S: D[v]:=min( D[v], D[v]+C[u,v] )

end.

Чтобы показать корректность алгоритма, надо доказать индукцией по размеру множества S, что для каждой вершины число D[v] равно длине кратчайшего пути из v₀ в v. Более того, для всех vV\S число D[v] равно длине кратчайшего пути из v₀ в v, лежащего целиком (если не считать саму вершину v) в S.

Базис индукции. Пусть S =1. Кратчайший путь из v₀ в себя имеет длину 0, а путь из v₀ в v, лежащий целиком (исключая v) в S, состоит из единственного ребра <v₀, v>.

Шаг индукции. Пусть u - узел для которого .

Если число D[u] не равно длине кратчайшего пути из v₀ в u, то должен быть более короткий путь P. Этот путь должен содержать вершину, отличную от u и не принадлежащую S. Пусть v - первая такая вершина на пути P из вершины v₀ в вершину u (смотрите рис. 3.9).

Но тогда расстояние от v₀ до v меньше D[u], а кратчайший путь в вершину v, целиком (исключая сам узел v) лежит в S. Следовательно, по предположению индукции, D[v] < D[u] в момент выбора u; таким образом, мы пришли к противоречию. Отсюда заключаем, что такого пути P нет и D[u] - длина кратчайшего пути из v₀ в u.

Второе утверждение (о том , что D[u] остается корректным) очевидно ввиду последнего оператора присваивания в алгоритме. 