Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

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

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

Шаг 1. перед началом выполнения алгоритма дуги не окрашены. Каждой вершине в ходе выполнения алгоритма присваивается число d (x), равное длине кратчайшего пути из s в x, включающего только окрашенные вершины.

Положить d (s) =0 и d (x) = для всех x, отличных от s. Окрасить вершину s и положить у=s (y-последняя из окрашенных вершин).

Шаг 2. Для каждой неокрашенной вершины x следующим образом пересчитать величину d (x):

(1)

Если d (x) = для всех неокрашенных вершин x, закончить процедуру алгоритма: в исходном графе отсутствуют пути из вершины s в неокрашенные вершины. В противном случае окрасить ту из вершин x, для которой величина d (x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину х (для этой дуги достигался минимум в соответствии с выражением (1)). Положить y=x.

Шаг 3. Если y=t, закончить процедуру: кратчайший путь из вершины s в вершину t найден (это единственный путь из s в t, составленный из окрашенных дуг). В противном случае перейти к шагу 2.

Отметим, что каждый раз, когда окрашивается некоторая вершина (не считая вершины s), окрашивается и некоторая дуга, заходящая в данную вершину. Таким образом, на любом этапе алгоритма Дейкстры в каждую вершину заходит не более чем одна окрашенная дуга. Кроме того, окрашенные дуги не могут образовывать в исходном графе цикл, так как в алгоритме не может окрашиваться дуга, концевые вершины которой уже окрашены. Следовательно, можно сделать вывод о том, что окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине s. Это дерево называется ориентированным деревом кратчайших путей. Единственный путь от вершины s до любой вершины x, принадлежащей дереву кратчайших путей, является кратчайшим путем между указанными вершинами.

Если кратчайшему пути из вершины s в вершину х в дереве кратчайших путей принадлежит вершина y, то часть этого пути, заключенная между x и y, является кратчайшим путем между этими вершинами. Действительно, если бы между х и у существовал более короткий путь, то упомянутый выше путь между вершинами s и x не могу бы быть кратчайшим.

Поскольку на всех этапах алгоритма Дейкстры окрашенные дуги образуют в исходном графе ориентированное дерево, алгоритм можно рассматривать как процедуру наращивания ориентированного дерева с корнем в вершине s. Когда в этой процедуре наращивания достигается вершина t, процедура может быть остановлена.

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