Алгоритм нахождения кратчайших маршрутов

Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины (s)до заданной конечной вершины (t), при условии, что такой путь существует.

Задачи данного типа имеют следующие модификации:

- для заданной начальной вершины s найти кратчайшие пути от s ко всем другим вершинам графа;

- найти кратчайшие пути между всеми парами вершин.

Для решения этих задач рассмотрим граф , , ребра которого имеют определенные веса (стоимости).

Веса ребер задаются матрицей . Элементы матрицы весов C могут быть положительными, отрицательными или нулями, поэтому для большинства алгоритмов поиска кратчайших маршрутов существует ограничение: в G не должно быть циклов с суммарным отрицательным весом (в этом случае кратчайшего маршрута не существует).

Например, если веса ребер графа G1 составляют соответственно , то имеется цикл суммарного отрицательного веса и задача не имеет решения.

Введем обозначения, пусть Г( ) – множество вершин графа G, которые смежны с вершиной .

Так, для графа G1 имеем Г(1)={2, 3}.

G1:

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

В общем случае этот метод основан на том, что вершинам приписываются временные пометки. Пометки обозначают длины путей от начальной вершины s к данной вершине (причем временные пометки являются верхними границами длин путей).

Величины этих пометок постепенно уменьшаются с помощью итерационной процедуры (т.е. процедуры, в которой постоянно повторяется некоторый набор операций).

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

Рассмотрим этот алгоритм для случая, когда вес каждого ребра графа неотрицателен ( ).