Пользуясь алгоритмом Дейкстры найти кратчайшие расстояния из вершины v1 неориентированного взвешенного графа в другие вершины графа

Метод Дейкстры нахождения кратчайшего пути состоит в том, что вершинам графа присваиваются временные метки, а затем временные метки заменяются постоянными.
На первом шаге вершине, принятую за первую, присваивается постоянная метка Lx=0, а всем остальным – временные метки ∞.
На всех последующих итерациях: пусть вершина vi на предыдущей итерации получила постоянную метку. Из множества вершин, смежных ей и не имеющих постоянной метки, вычисляются новые метки по формуле:
Lновvj=min⁡{Lстvj,L*vi+cvi,vj}
где Lнов(vj)-новая временная метка;
Lстvj-старая временная мета;
L*vi- постоянная метка вершины, принадлежащей множеству вершин, имеющих такую метку.
cvi,vj-вес ребра, соединяющего вершины vi и vj;
После этого из все временных меток выбирается наименьшая, и именно она станет следующей постоянной . Процесс продолжается до тех пор, пока не будут найдены постоянные метки для всех вершин.
Результаты удобнее представить таблицей:
Вершины Итерации
0 1 2 3 4 5
v1
0*
v2
∞
1*
v3
∞
3 3 2*
v4
∞
8 8 3 3*
v5
∞
∞
∞
3 3 3*
v6
∞
1 1*
На нулевой итерации присваиваем постоянную метку 0 исходной вершине v1;
На первой итерации из всех последователей вершины v1 даем постоянную метку вершине v2 с наименьшим весом;
На второй итерации для всех смежных с вершиной v2 вершин, не имеющих постоянной метки V={v3} вычисляем новые метки:
Lновv3=min3;1+2=3
Из всех вершин, имеющих временную метку, выбираем вершину с наименьшей меткой – вершина v6, поэтому присваиваем ей постоянную метку Lv6=1.
На третьей итерации для всех смежных с вершиной v6 вершин, не имеющих постоянной метки V={v3;v4;v5} вычисляем новые метки:
Lновv3=min⁡{3, 1+1}=2
Lновv4=min⁡{8, 1+2}=3
Lновv5=1+2=3
Из всех вершин, имеющих временную метку, выбираем вершину с наименьшей меткой – вершина v3, поэтому присваиваем ей постоянную метку Lv3=2.
На четвертой итерации для всех смежных с вершиной v3 вершин, не имеющих постоянной метки V={v4} вычисляем новые метки:
Lновv4=min3;2+1=3
Из всех вершин, имеющих временную метку, выбираем вершину с наименьшей меткой – вершина v4, поэтому присваиваем ей постоянную метку Lv4=3.
На последней итерации находим постоянную метку L(v5)=3.
Восстанавливаем кратчайший маршрут от вершины v1 в вершину v4 (таких маршрута два):
v1→v6→v4
v1→v6→v3→v4