Решение 1 задачи. Оптимизационные задачи на графах.

Задачи на алгоритмы с графами
Иходные данные
Var: vb ---> v
Список ребер ПРОСТОГО графа и их веса в виде
w({vi, vj}) =
Означает, что ребро из вершин vi и vj имеет вес W
Веса — целые неотрицательные числа с обычными операциями сложения и сравнения
Число вершин равно максимальному номеру вершины в списке
Других ребер, кроме упомянутых в списке, нет
Необходимо
(1) По алгоритму Флойда-Уоршалла найти матрицу весов маршрутов И матрицу номеро
первых вершин этих маршрутов. Обратите внимание, граф простой, поэтому каждо
ребро «проходимо» в любом направлении. То есть, если указано, например
w({v2, v5}) = 12
то возможен как маршрут через вершины 2 и 5, так и в обратном направлении чере
5 и 2. В обоих случаях вес ребра равен 12. Поэтому матрица весов симметричная
(2) Для указанной пары вершин vb ---> vt извлечь из матрицы маршрутов маршрут о
вершины vb к вершине vt в виде последовательности номеров вершин
(3) По алгоритму Дейкстры для этой же пары вершин найти вес и маршру
минимального веса
(4) По алгоритму Прима для данного графа найти минимальный остов в виде списк
ребер остова
В отчетах приведите протоколы вычилений (последовательности промежуточны
состояний вычислений)