СибГУТИ Лабораторная работа 2 Вариант 8 Теория сложности вычислительных процессов и структур скачать бесплатно

Задание

Написать программу, которая по алгоритму Дейкстры (если Ваша фамилия начинается с гласной буквы) или Форда-Беллмана (если Ваша фамилия начинается с согласной буквы) находит кратчайшее расстояние от вершины с номером Вашего варианта до всех остальных вершин связного взвешенного неориентированного графа, имеющего 10 вершин (нумерация вершин начинается с 0).

Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.

Вывести все найденные кратчайшие расстояния и соответствующие им пути (в виде последовательности ребер).

Номер варианта выбирается по последней цифре пароля.

Вариант 8

0 11 0 0 1 1 4 0 0 3

11 0 5 6 6 8 5 11 4 8

0 5 0 3 9 6 6 9 2 11

0 6 3 0 7 6 3 7 11 8

1 6 9 7 0 3 3 9 9 0

1 8 6 6 3 0 9 3 1 7

4 5 6 3 3 9 0 3 7 10

0 11 9 7 9 3 3 0 0 3

0 4 2 11 9 1 7 0 0 10

3 8 11 8 0 7 10 3 10 0

Описание алгоритма Форда-Беллмана

Формируем массив – минимально возможная стоимость переезда (перехода, перевозки) из вершины v0 в vi на каждом этапе работы нашего алгоритма.

Первоначально он задается как .

Затем пересчитываем стоимости всех вершин по формуле до тех пор, пока система не стабилизуется (так называемое транзитивное замыкание). В результате мы получим стоимости переезда из каждой вершины графа до заданной v0 и эти стоимости будут минимально возможными.

Текст программы на языке Pascal

...

Результаты работы программы

Кратчайшие расстояния:

До вершины 0: 2; путь: (0, 5) (5, 8)

До вершины 1: 4; путь: (1, 8)

До вершины 2: 2; путь: (2, 8)

о вершины 3: 5; путь: (3, 2) (2, 8)

До вершины 4: 3; путь: (4, 0) (0, 5) (5, 8)

До вершины 5: 1; путь: (5, 8)

До вершины 6: 6; путь: (6, 0) (0, 5) (5, 8)

До вершины 7: 4; путь: (7, 5) (5, 8)