Взвешенный граф задан матрицей длин дуг. Нарисовать граф

Матрица симметрична относительно главной диагонали, поэтому граф неориентированный.
Построим граф, упорядочив вершины.
Рисунок 7.
а) Найдем остов минимального веса (минимальное остовное дерево) используя алгоритм Краскала.
Минимальный вес ребра в данном графе равен 2.
Введем ребра веса 2, так, чтобы не образовать циклы.
Введем в дерево ребра минимального веса [v1, v3],[v1, v4],[v5, v6].
Введем вершины v1, v3, v4,v5, v6
G1 = v1, v3, v4,v5,v6, ,[v1, v3], [v1, v4], [v5, v6]
Ребер веса 2 больше нет.
Теперь введем ребра веса 3, так, чтобы не образовать циклы.
2.Введем в дерево ребра веса 3 [v1, v6],[v2, v4]. Введем вершину v2
G2 = v1, v2, v3, v4,v5,v6,[v1, v3], [v1, v4], [v5, v6],[v1, v6], [v2, v4]
Все вершины включены в дерево. Количество рёбер в дереве 6-1=5. Алгоритм закончен.
Вес минимального остовного дерева = 2+2+2+3+3=12
Ребра минимального остовного дерева: (1,4), (1,3), (1,6), (6,5), (4,2)
Рисунок 8.
б) Воспользуемся алгоритмом Дейкстры нахождения критического пути.
Пусть задан взвешенный граф , неотрицательные веса на дугах которого будем интерпретировать как расстояния от вершины до вершины . Длиной пути называется сумма длин составляющих путь дуг. Требуется найти кратчайший путь из вершины в вершину .
В процессе работы алгоритма каждая вершина имеет метку, которая может быть временной или постоянной . Временная метка есть длина некоторого пути из в , возможно не оптимального. В процессе работы алгоритма временные метки могут изменяться, уменьшаясь, когда удается найти более короткий путь. На каждом шаге алгоритма вершина , имеющая минимальную временную метку получает постоянную метку . Постоянная метка есть длина кратчайшего пути из в , в дальнейшем она не меняется.
В начальный момент вершина имеет постоянную метку , а все остальные вершины графа – временные метки . На первом шаге алгоритма каждая вершина , для которой существует дуга , получает временную метку (помечается из вершины ). Затем вершина , для которой имеет минимальное значение, получает постоянную метку (если минимум достигается на нескольких вершинах, то берется любая из них)