Шпоры по МПиПА / Графы / Путь минимального веса в нагруженном графе / Pascal / Описание / Путь минимального веса в нагруженном графе

Путь минимального веса в нагруженном графе.

Входные данные функции – число вершин графа, матрица весов пути (число на позиции i,j характеризует вес пути из вершины i в вершину j; если указана -1 – путь не существует) и вершины, между которыми нужно определить путь минимального веса.

Выходные данные функции – вектор, содержащий маршрут в обратном порядке (то есть сначала – последняя вершина, затем предпоследняя и т.д.), если путь найден (в противном случае – первая координата вектора равна -1). Кроме того, внутри функции определяется вес пути и его длина, то есть количество пройденных вершин.

Код: MinWay.pas.

Исполняемый файл: MinWay.exe.

Примеры использования:

Wave algoritm.

Enter graph dimension: 5

Enter graph weightMatrix:

Enter 1 row: -1 1 4 -1 10

Enter 2 row: -1 -1 2 -1 -1

Enter 3 row: -1 -1 -1 1 5

Enter 4 row: -1 -1 -1 -1 3

Enter 5 row: -1 -1 -1 -1 -1

Enter From Node: 1

Enter To Node: 5

Question: Exist way from 1 to 5?

Answer: way from 1 to 5: 1 -> 2 -> 3 -> 4 -> 5

Weight: 7

Press Enter to continue...

Wave algoritm.

Enter graph dimension: 6

Enter graph weightMatrix:

Enter 1 row: -1 -1 -1 -1 15 -1

Enter 2 row: 1 -1 -1 20 -1 30

Enter 3 row: -1 -1 -1 2 -1 20

Enter 4 row: -1 -1 -1 -1 -1 4

Enter 5 row: -1 -1 1 -1 -1 -1

Enter 6 row: -1 -1 -1 -1 -1 -1

Enter From Node: 2

Enter To Node: 6

Question: Exist way from 2 to 6?

Answer: way from 2 to 6: 2 -> 1 -> 5 -> 3 -> 4 -> 6

Weight: 23

Press Enter to continue...