2.4.2. Алгоритм Форда

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

Рис. 2.8

Например, при поиске путей из вершины 1 для графа, изображенного на рис 2.8, вершина 1 получит метку 0, вершины 2 и 3 – метки 2 и 1. Далее минимальной будет метка вершины 3, и вершина 4 получит метку 2, которая в дальнейшем не изменится, поскольку вершина 3 уже просмотрена. Между тем кратчайший путь в 4 проходит через вершины 1,2,3,4 и имеет длину 1. Более того, при наличии ребер отрицательной длины в графе может присутствовать контур отрицательной длины, и тогда кратчайших путей вообще не существует, поскольку длину пути всегда можно уменьшить, добавляя к нему несколько обходов этого контура.

Рис. 2.9

Алгоритм Форда представляет собой простую модификацию алгоритма Дийкстры для случая, когда длины ребер могут быть отрицательными. На шаге 4 алгоритма следует проводить вычисление новых меток не для kS, а для всех соседних сnвершин. Если при этом изменяется метка у вершины, уже входящей в множествоS, то ее следует снова исключить изS. Таким образом, одна вершина может быть просмотрена несколько раз. Если в графеNвершин, то простой путь не может содержать более чемNвершин. Следовательно, если при раборе алгоритма Форда какая-либо вершина просматривается более чемNраз, это значит, что в графе имеется контур отрицательной длины.

Пример 3. Для графа на рис. 2.9 вычисление длин кратчайших путей из вершины 1 с помощью алгоритма Форда дает следующие результаты. Выделены метки вершин, входящих в S.

При выполнении алгоритма некоторые вершины просматриваются несколько раз. Дерево кратчайших путей представлено на рис. 2.9.