Курсовой проект «Комбинаторные алгоритмы. Поиск кратчайшего пути на графе.»

Поиск кратчайшего пути на графе

Кратчайший путь рассматривается при помощи математического объекта, называемого графом.

Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:

1. 
   Алгоритм Дейкстры;
   
2. 
   Алгоритм Флойда — Уоршелла;
   
3. 
   Алгоритм Беллмана — Форда.
   

Принцип работы некоторых из указанных алгоритмов будет рассмотрен в рамках данной работы.

Постановка задачи

Задачей является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.

Пользователь вводит количество вершин и длины рёбер графа, а после обработки этих данных на экран выводится кратчайший путь между двумя ранее заданными вершинами и его длина.

Описание задачи

Алгоритм Дейкстры

Данный алгоритм был изобретён нидерландским ученым Э. Дейкстрой в 1959 году.
Каждой вершине сопоставим метку — минимальное известное расстояние от этой вершины до начальной, с которой мы начинаем поиск кратчайшего пути. Алгоритм работает пошагово — на каждом шаге он посещает одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка начальной вершины полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от начальной до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина, имеющая минимальную метку. Обозначим её за U. Мы рассматриваем всевозможные маршруты, в которых U является предпоследним пунктом. Вершины, в которые ведут рёбра из U, назовем соседями этой вершины. Для каждого соседа вершины U, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки U и длины ребра, соединяющего U с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину U как посещенную и повторим шаг алгоритма.
С ложность алгоритма в простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, время работы алгоритма есть