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

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

1. На шаге 2 алгоритма Дейкстры пересчет пометок осуществляется для всех вершин графа (как для вершин с временными метками, так и для вершин с постоянными метками)

2. Если для некоторой вершины vi с постоянной меткой происходит уменьшение пометки l( ), то это пометка становится временно, а пометка Q( ) уничтожается.

3. Алгоритм заканчивает работу тогда, когда все вершины получаются постоянные метки и после выполнения шага 2 алгоритма Дейкстры ни одна из меток не меняется.

П

ример. Определить кратчайший путь на взвешенном графе между вершинами и .

Решение.

1.Помечаем в соответствии с алгоритмом вершины графа, l( )=0, l( )=l( )= Вершине приписываем постоянную пометку p= = .

2. Из вершины помечаем остальные вершины l( )=0, l( )=2, l( )=1. у вершин и уменьшились пометки, следовательно Q( )= , Q( )= . Вершине приписываем постоянную пометку p= .

3. Из вершины v3 помечаем остальные вершины: l( )=0, l( )=2, l( )=1. Вершине приписываем постоянную пометку p= .

4. Из вершины помечаем остальные вершины:

l( )=0, l( )=2, l( )=0. У вершины уменьшилась пометка, следовательно Q( )= . Пометка вершины стала временной. Пометка Q( )= уничтожается.

5. Так как имеется всего одна вершина с временной пометкой, это вершина , то ей приписывается постоянная пометка, т.е. p= . Из вершины помечаем остальные вершины: l( )=0, l( )=2, l( )=0. Пометки вершин и не изменились.

6. Выполняем еще раз шаг 2 алгоритма Дейкстры: l( )=0, l( )=2, l( )=0. Остановка алгоритма, так как все вершины получили постоянные пометки, и после выполнения очередного шага ни одна из пометок не изменилась.

Восстанавливаем по меткам Q кратчайший путь из вершины = в : путь длиной l( , )=0.