Лабораторной работе №4. Алгоритмы и структуры данных. Тема: Графы. ЛЭТИ.

Лабораторной работе №4. Алгоритмы и структуры данных.
Тема: Графы. ЛЭТИ.
Вариант 35

Содержание
Введение ........................................................................................................ 3
Задание ........................................................................................................... 3
Постановка задачи и описание решения ..................................................... 3
Контрольные тесты ...................................................................................... 5
Вывод ............................................................................................................. 8
Список использованных источников........................................................... 9
Текст программы ........................................................................................... 10


Цель работы
Исследование алгоритмов для работы с ориентированными графами
Задание
Отыскание кратчайшего пути между заданной парой вершин в произвольном ориентированном графе с нагруженными ребрами
Математическая формулировка: ориентированный граф G = <V, E>, заданный в форме весового списка ребер edge [v, u], который может содержать циклы с отрицательной длиной, и вершина-источник s. Результатом является вектор расстояний d.
Постановка задачи и описание решения
Для алгоритма Форда-Беллмана более удобно представлять граф в виде списка всех рёбер (вектор структур ребра). Для такого алгоритма матрица смежности получается довольно трудно затратной.
Было решено сделать меню, в котором пользователь выбирает характеристики графа: в первом подменю он выбирает, вводить ли ему вручную или позволить компьютеру сгенерировать граф: если пользователь выбрал первый вариант, то он просто вводит данные графа с клавиатуры, иначе выводится следующее меню, в котором пользователь выбирает, какими должны быть числа в графе: положительными или положительными и отрицательными (это было сделано для того, чтобы удостовериться в правильности алгоритма Беллмана - Форда) – в таком случае генерируются однозначные числа (чтобы красиво выводилась “матрица” и наглядно показать действие алгоритма, ведь для демонстрации алгоритма можно использовать и целые числа)
Важное уточнение: если между вершинами связи нет, то вводится и выводится именно ноль
Формируется список ребер размером n*n, где n – кол-во ребер (однако обрабатываться будут только ребра с ненулевым весом, поэтому одна итерация будет повторяться [кол-во ребер] раз)
Заведём массив расстояний d[n], который после обработки будет содержать ответ на задачу: сначала мы заполняем расстояние вершины старта нулем, остальные бесконечностью. Если после действий алгоритма расстояние все равно бесконечности, значит, что эта вершина недостижима
Также в программе была учтена возможность обнаружения отрицательного цикла – такого, что алгоритм может бесконечно улучшать свою оценку, уходя в минус бесконечность.
Для восстановления пути был инициализирован p[n], в котором соответствующие вершины будут хранить предшественника. Алгоритм, предполагая, что кратчайшее расстояние до одной вершины уже посчитано, пытается улучшить кратчайшее расстояние до другой вершины. Следовательно, в момент улучшения нам надо просто запоминать в массиве “предков”, из какой вершины это улучшение произошло.
Общая сложность алгоритма – О(ne), где n – кол-во вершин, e - кол-во ребер, однако в худшем случае она может достигать O(n^3) (так как тройной цикл)

2020