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

Теория сложности вычислительных процессов и структур
Лабораторная работа №2
Поиск кратчайшего расстояния между двумя вершинами
Присылаемый на проверку архив должен содержать 2 файла:
 файл отчета, содержащий титульный лист, условие задачи, описание используемого алгоритма, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
 файл с исходным текстом программы (программу можно писать на любом языке программирования).

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

2. Теоретическая часть и описание алгоритма Форда-Беллмана
Алгоритм Форда-Беллмана — это эффективный метод динамического программирования для поиска кратчайших путей из одной фиксированной вершины-источника во все остальные вершины взвешенного графа. В отличие от алгоритма Дейкстры, данный метод корректно работает с графами, содержащими ребра с отрицательным весом.
Суть алгоритма:
Алгоритм последовательно улучшает (релаксирует) текущее знание о кратчайших расстояниях. Для графа с количеством вершин V кратчайший путь без циклов не может содержать более чем (V - 1) ребро. Поэтому алгоритм выполняет ровно (V - 1) итераций.

Пошаговое описание:
1. Инициализация: создается массив расстояний D размера V. Для стартовой вершины-источника расстояние D[start] принимается равным 0, для всех остальных вершин расстояние инициализируется бесконечностью (практически — очень большим числом). Также инициализируется массив предков P для последующего восстановления маршрутов.
2. Основной цикл (Релаксация рёбер): выполняется (V - 1) внешних итераций. На каждой итерации перебираются абсолютно все рёбра графа (u, v) с весом W. Выполняется проверка условия релаксации:
o Если D[u] + W < D[v], то мы нашли более короткий путь к вершине v через вершину u. Расстояние обновляется: D[v] = D[u] + W, а в массив предков записывается P[v] = u.
3. Восстановление путей: на основе заполненного массива предков P для каждой вершины выполняется обратный обход от целевой вершины к стартовой, формируя точную последовательность пройденных рёбер.

3. Исходные данные (Вариант 6)
Граф состоит из 10 вершин (пронумерованных от 0 до 9). Стартовая вершина-источник: 6.
Матрица смежности из задания имеет следующий вид:
Вершины 0 1 2 3 4 5 6 7 8 9
0 0 0 8 8 7 5 5 6 1 2
1 0 0 3 1 6 3 7 3 0 9
2 8 3 0 11 2 3 0 8 1 10
3 8 1 11 0 6 4 0 11 7 9
4 7 6 2 6 0 2 11 6 3 4
5 5 3 3 4 2 0 2 1 3 3
6 5 7 0 0 11 2 0 3 3 7
7 6 3 8 11 6 1 3 0 0 8
8 1 0 1 7 3 3 3 0 0 8
9 2 9 10 9 4 3 7 8 8 0
Примечание: значение 0 на пересечении строки 6 и столбцов 2 и 3 означает, что прямых рёбер из вершины 6 в вершины 2 и 3 не существует.

Лабораторная работа 2 20.09.2026 20.09.2026 Зачет Уважаемый, замечаний нет. Галкина Марина Юрьевна