Выбор оптимального маршрута по алгоритму Дейкстры

Алгоритм Дейкстры предназначен для нахождения кратчайшего пути между вершинами в неориентированном графе.

Идея алгоритма следующая: сначала выбирается путь до начальной вершины равным нулю, эта вершина заносится во множество уже выбранных, расстояние от которых до оставшихся невыбранных определено. На каждом этапе находится следующая невыбранная вершина, расстояние до которой наименьшее, и соединённая с какой-нибудь вершиной из множества выбранных (это расстояние будет равно расстоянию до уже выбранной вершины плюс длина ребра)[2, 3].

В качестве примера рассмотрим задачу нахождения кратчайшего пути от вершины A до вершины D для графа на Рис.6.

Рис.6. Взвешенный неориентированный граф.

На Рис.7 представлен фрагмент рабочего листа приложения MS Excel, на котором реализован алгоритм Дейкстры для сформулированной задачи.

Шаг 1-ый. Выбираем вершину A. Выбранная вершина напрямую связана с вершинами B и C. Расстояние до B равно 7, а до C – 10. Поэтому дополняем множество выбранных вершин вершиной B.

Шаг 2-ой. От выбранного множества A и B кратчайшее прямое расстояние до вершины F. Поэтому дополняем множество выбранных вершин вершиной F.

Шаг 3-ий. От выбранного множества A, B и F кратчайшее прямое расстояние до вершины E. Дополняем множество выбранных вершин вершиной E.

Шаг 4-ый. От выбранного множества A, B,F и E кратчайшее прямое расстояние до вершины H. Дополняем множество выбранных вершин вершиной H.

Шаг 5-ый. От выбранного множества A, B, F, E и H кратчайшее прямое расстояние до вершины G. Дополняем множество выбранных вершин вершиной G.

Шаг 6-ой. От выбранного множества A, B, F, E, H и G кратчайшее прямое расстояние до вершины I. Дополняем множество выбранных вершин вершиной I.

Рис.7. Поиск кратчайшего пути с помощью алгоритма Дейкстры.

Шаг 7-ой. От выбранного множества A, B, F, E, H, G и I кратчайшее прямое расстояние до вершины целевой вершины B. Процесс нахождения минимального расстояния завершён.

Выбор траектории осуществляется просмотром сформированной таблицы в обратном порядке и представлен наглядно на Рис.8.

Итак, минимальная длина пути от вершины A до вершины D составляет 44 условных единиц. Траектория кратчайшего пути (A, B, F,H, D).

Рис.8. Выбор оптимальной траектории.