Нагруженный граф задан матрицей длин дуг Ck(G)

Для наглядности изобразим граф на плоскости:
а) Для построения минимального остовного дерева упорядочим ребра по неубыванию весов:
v2, v5, 1, v3, v6, 1, v4, v6, 1, v1, v4, 2, v2, v6, 2, v1, v5, 3, v2, v3, 3,
v1, v6,4, v4, v5, 4, {v3, v4, 5}
Будем поочередно добавлять ребра в остовное дерево при условии, что они не будут образовывать цикл с уже имеющимися в остове ребрами. Прекратим добавление, когда количество ребер в остове будет равно 6-1=5.
Шаг 1 . Добавляем ребро v2, v5, 1
Шаг 2. Добавляем ребро v3, v6, 1
Шаг 3. Добавляем ребро v4, v6, 1
Шаг 4. Добавляем ребро v1, v4, 2
Шаг 5. Добавляем ребро v2, v6, 2
Получили минимальный остов. На рисунке выделен жирным. Вес остова равен 7.
б) Воспользуемся алгоритмом Дейкстры для нахождения кратчайшего пути.
Будем заполнять таблицу метками вершин на каждом шаге алгоритма.
v
d(v)
p(v)
v1
v2
v3
v4
v5
v6
0
∅
-
-
∞
∞
∞
∞
0
∞
1
v5
0
-
3
1
∞
4
-
∞
2
v2
1
v5
3
-
4
4
-
3
3
v1
3
v5
-
-
4
4
-
3
4
v6
3
v2
-
-
4
4
-
-
5
v3
4
v2
-
-
-
4
-
-
6
v4
4
v5
-
-
-
-
-
-
-
Шаг 0