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

Задачи на алгоритмы с графами.

Исходные данные:

Var 4 : v7 ---> v8

w({v1,v3})=16, w({v1,v5})=12, w({v1,v6})=6, w({v1,v8})=13, w({v2,v3})=18,

w({v2,v4})=23, w({v2,v6})=17, w({v3,v5})=29, w({v3,v6})=31, w({v4,v6})=27,

w({v4,v7})=3, w({v5,v6})=24, w({v6,v7})=2, w({v6,v8})=1.

Список ребер ПРОСТОГО графа и их веса в виде:

w({vi, vj}) = W

Означает, что ребро из вершин vi и vj имеет вес W.

Веса — целые неотрицательные числа с обычными операциями сложения и сравнения.

Число вершин равно максимальному номеру вершины в списке.

Других ребер, кроме упомянутых в списке, нет.

Необходимо:

(1) По алгоритму Флойда-Уоршалла найти матрицу весов маршрутов И матрицу номеров

первых вершин этих маршрутов. Обратите внимание, граф простой, поэтому каждое

ребро «проходимо» в любом направлении. То есть, если указано, например,

w({v2, v5}) = 12,

то возможен как маршрут через вершины 2 и 5, так и в обратном направлении через

5 и 2. В обоих случаях вес ребра равен 12. Поэтому матрица весов симметричная.

(2) Для указанной пары вершин vb ---> vt извлечь из матрицы маршрутов маршрут от

вершины vb к вершине vt в виде последовательности номеров вершин.

(3) По алгоритму Дейкстры для этой же пары вершин найти вес и маршрут

минимального веса.

(4) По алгоритму Прима для данного графа найти минимальный остов в виде списка

ребер остова.

В отчетах приведите протоколы вычислений (последовательности промежуточных

состояний вычислений).