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

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

Var 6 : v1 ---> v4 w({v1,v2})=32, w({v2,v5})=6, w({v2,v8})=28, w({v3,v4})=13, w({v3,v6})=8, w({v3,v7})=19, w({v3,v8})=9, w({v4,v8})=20, w({v5,v7})=2, w({v5,v8})=18, w({v6,v7})=27, w({v6,v8})=23, w({v7,v8})=5.