Результат работы программы
Рисунок 1 – Матрица весов ребер
Результат работы программы
Меняем путь до вершины 14 через вершину 0 со стоимостью ребра 8
Меняем путь до вершины 1 через вершину 0 со стоимостью ребра 200
################ Итерация окончена #############
Меняем путь до вершины 3 через вершину 14 со стоимостью ребра 1
Меняем путь до вершины 12 через вершину 14 со стоимостью ребра 14
Меняем путь до вершины 5 через вершину 14 со стоимостью ребра 19
Меняем путь до вершины 7 через вершину 14 со стоимостью ребра 22
Меняем путь до вершины 13 через вершину 1 со стоимостью ребра 28
Меняем путь до вершины 6 через вершину 14 со стоимостью ребра 29
Меняем путь до вершины 8 через вершину 14 со стоимостью ребра 29
Меняем путь до вершины 2 через вершину 1 со стоимостью ребра 200
Меняем путь до вершины 13 через вершину 14 со стоимостью ребра 200
################ Итерация окончена #############
Меняем путь до вершины 13 через вершину 8 со стоимостью ребра 1
Меняем путь до вершины 11 через вершину 2 со стоимостью ребра 7
Меняем путь до вершины 11 через вершину 3 со стоимостью ребра 9
Меняем путь до вершины 10 через вершину 6 со стоимостью ребра 10
Меняем путь до вершины 13 через вершину 5 со стоимостью ребра 10
Меняем путь до вершины 10 через вершину 7 со стоимостью ребра 12
Меняем путь до вершины 4 через вершину 6 со стоимостью ребра 15
Меняем путь до вершины 9 через вершину 13 со стоимостью ребра 17
Меняем путь до вершины 9 через вершину 6 со стоимостью ребра 24
Меняем путь до вершины 9 через вершину 3 со стоимостью ребра 27
Меняем путь до вершины 4 через вершину 3 со стоимостью ребра 28
Меняем путь до вершины 2 через вершину 3 со стоимостью ребра 200
################ Итерация окончена #############
Меняем путь до вершины 2 через вершину 11 со стоимостью ребра 7
Меняем путь до вершины 4 через вершину 11 со стоимостью ребра 13
Меняем путь до вершины 1 через вершину 13 со стоимостью ребра 28
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
################ Итерация окончена #############
Рисунок 3 – Матрица длин путей и минимальный путь до выбранной вершины
Выводы
В ходе лабораторной работы, мы ознакомились с двумя алгоритмами построения минимального пути до вершин: алгоритм Дейкстры и алгоритм Беллмана-Форда, а также написали программу для построения минимального пути по алгоритму Беллмана-Форда на языке программирования C++.