Метод Форда-Беллмана решение задачи о кратчайшем пути в графе.

Алгоритм Форда-Беллмана

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

Описание алгоритма

Мы считаем, что граф не содержит цикла отрицательного веса.

Заведём массив расстояний $d[0 ldots n-1]$ , который после отработки алгоритма будет содержать ответ на задачу. В начале работы мы заполняем его следующим образом: $d[v] = 0$ , а все остальные элементы $d[]$ равны бесконечности $infty$ .

Сам алгоритм Форда-Беллмана представляет из себя несколько фаз. На каждой фазе просматриваются все рёбра графа, и алгоритм пытается произвести релаксацию (relax, ослабление) вдоль каждого ребра $(a,b)$ стоимости $c$ . Релаксация вдоль ребра — это попытка улучшить значение $d[b]$ значением $d[a] + c$ . Фактически это значит, что мы пытаемся улучшить ответ для вершины $b$ , пользуясь ребром $(a,b)$ и текущим ответом для вершины $a$ .

Утверждается, что достаточно $n-1$ фазы алгоритма, чтобы корректно посчитать длины всех кратчайших путей в графе (повторимся, мы считаем, что циклы отрицательного веса отсутствуют). Для недостижимых вершин расстояние $d[]$ останется равным бесконечности $infty$ .

Случай отрицательного цикла

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

Нетрудно понять, что алгоритм Форда-Беллмана сможет бесконечно делать релаксации среди всех вершин этого цикла и вершин, достижимых из него. Следовательно, если не ограничивать число фаз числом $n-1$ , то алгоритм будет работать бесконечно, постоянно улучшая расстояния до этих вершин.

Отсюда мы получаем критерий наличия достижимого цикла отрицательного веса: если после $n-1$ фазы мы выполним ещё одну фазу, и на ней произойдёт хотя бы одна релаксация, то граф содержит цикл отрицательного веса, достижимый из $v$ ; в противном случае, такого цикла нет.

Более того, если такой цикл обнаружился, то алгоритм Форда-Беллмана можно модифицировать таким образом, чтобы он выводил сам этот цикл в виде последовательности вершин, входящих в него. Для этого достаточно запомнить номер вершины $x$ , в которой произошла релаксация на $n$ -ой фазе. Эта вершина будет либо лежать на цикле отрицательного веса, либо она достижима из него. Чтобы получить вершину, которая гарантированно лежит на цикле, достаточно, например, $n$ раз пройти по предкам, начиная от вершины $x$ . Получив номер $y$ вершины, лежащей на цикле, надо пройтись от этой вершины по предкам, пока мы не вернёмся в эту же вершину $y$ (а это обязательно произойдёт, потому что релаксации в цикле отрицательного веса происходят по кругу).

Програмная реализация и примеры расписанны на этих сайтах:

1) http://urban-sanjoo.narod.ru/bellman-ford.html
2) http://e-maxx.ru/algo/ford_bellman