Лабораторная работа №6. Структуры и алгоритмы обработки данных. Нахождение кратчайших путей в графе. Алгоритм Дейкстры.

Лабораторная работа №6. Структуры и алгоритмы обработки данных. Нахождение кратчайших путей в графе. Алгоритм Дейкстры.


Постановка задачи:
Найти кратчайший путь между двумя фиксированными вершинами заданного графа с помощью алгоритма Дейкстры.

Теория
Задача о кратчайшем пути – задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.

Алгоритм нахождения кратчайшего пути между двумя фиксированными вершинами графа
1. Задаем метки всех вершин максимально возможными значениями.
2. Метку начальной вершины задаем нулем.
3. Текущую вершину задаем значением начальной вершиной.
4. Пока не посещены все вершины графа:
4.1.  Посещаем вершину.
4.2.  Если текущая вершина равна конечной вершине, то
4.2.1. Переходим к шагу 5.
4.3.  Перебираем все смежные вершины текущей вершины:
4.3.1. Новую метку задаем суммой метки текущей вершины и расстоянием от смежной вершины к текущей вершине.
4.3.2. Если новая метка меньше метки текущей вершины, то
4.3.2.1. Метке текущей вершины задаем значение новой метки.
4.4.  Текущей вершине задаем значение не посещённой вершины с наименьшим значением метки.
5. Заносим в стек вершин кратчайшего пути конечную вершину.
6. Пока вершина стека не равна начальной вершине:
6.1.  Перебираем все смежные вершины вершины стека:
6.1.1. Если метка смежной вершины равна разности метки вершины стека и расстоянием от смежной вершиной к вершине стека, то
6.1.1.1. Заносим смежную вершину в стек.
6.1.1.2. Переходим к шагу 6.2.
6.2.  Если ни одна смежная вершина не была занесена в стек вершин кратчайшего пути, то
6.2.1. Выводим сообщение «Между вершинами нет пути».
6.2.2. Завершаем алгоритм.
7. Выводим кратчайший путь на экран.
8. Выводим метку конечной вершины (длину пути) на экран.

Входные данные:
• matrix[,] – матрица смежности графа.
• start – номер начальной вершины.
• end – номер конечной вершины.

Выходные данные:
• status – текстовое поле для вывода вершин кратчайшего пути между вершинами и длины пути.
• path – стек для хранения вершин кратчайшего пути между вершинами.
• distance – длина кратчайшего пути между заданными вершинами.

2020