Лабораторной работе №5. По дисциплине Алгоритмы и структуры данных. Тема Нахождение кратчайшего пути в графе.

Лабораторной работе No5. По дисциплине Алгоритмы и структуры данных. Тема Нахождение кратчайшего пути в графе.


Цель работы: ознакомление с вариантами реализации алгоритмов на графах на примере задачи поиска кратчайшего пути в неориентированном графе.
Теоретические положения
Алгоритм Беллмана-Форда:
Алгоритм использует метод динамического программирования и формирует решение в виде квадратной матрицы, количество строк и столбцов которой равно количеству вершин графа. Ячейка на пересечении строки “m” и столбца “n” после окончания расчета содержит длину кратчайшего путь от заданной вершины до вершины «m», при условии, что он (путь) содержит не более «n» ребер (считая номера столбцов с «0»).
Матрица заполняется по столбцам слева направо. Начальное заполнение содержит нулевой столбец, где для строки заданной (исходной) вершины установлено значение «0», а для всех остальных строк – значение «∞» (на практике используется достаточно большая по величине константа).
Алгоритм Дейкстры:
Алгоритм последовательно анализирует («обрабатывает») все вершины графа, начиная от заданной (исходной) следующим образом.
Изначально всем вершинам, кроме исходной, присваивается оценка длины кратчайшего пути, равная «∞», (исходной вершине присваивается оценка «0»). Все вершины считаются «необработанными».
В каждой итерации цикла среди необработанных вершин выбирается одна, имеющая наименьшую на текущий момент оценку кратчайшего пути от заданной (исходной). Анализируются все ребра, исходящие от нее в сторону необработанных вершин, и если какое-либо из ребер улучшает (уменьшает) текущую оценку, то эта оценка обновляется.

2022