Служба спасения студентов
Служба спасения для студентов

СибГУТИ Лабораторная работа 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)
До вершины 8: 0; путь: (8, 8)
До вершины 9: 5; путь: (9, 0) (0, 5) (5, 8)
Заявка на расчет