Этот алгоритм ищет кратчайшие расстояния от одной вершины до всех остальных во взвешенном графе за время O(N3) если граф задан матрицей смежности или за O(MN) для графа на списке рёбер.
Для работы этого алгоритма нам дополнительно потребуется лишь массив расстояний D: array[1..MaxN] of Longint.
Алгоритм Форда-Беллмана несколько похож на алгоритм Дейкстры: у него тоже на I-ой итерации в элементе D[J] хранится длина кратчайшего пути из стартовой вершины в J-ую, состоящего не более чем из I рёбер. Но на каждой итерации происходят релаксации сразу по всем рёбрам. Именно из-за этого, если не вдаваться в подробности, он работает даже для графов с отрицательными весами рёбер, хотя и асимптотически медленнее, чем алгоритм Дейкстры.
Ниже приведена его реализация для графа, представленного списком рёбер (здесь I, J: Integer, а Х - номер стартовой вершины):
|
1 2 3 4 5 6 |
For I := 1 to N do D[I] := Inf; D[X] := 0; For I := 1 to N do For J := 1 to M do If D[R[J].B] > D[R[J].A] + R[J].C Then D[R[J].B] := D[R[J].A] + R[J].C; |
В строках 1-3 аналогично алгоритму Дейкстры инициализируется массив D, правда здесь нам не нужен нулевой элемент этого массива. В строке 4 запускается N итераций алгоритма, в строках 5-6 производится релаксация по всем рёбрам графа.
Поскольку алгоритм работает также на графах с отрицательными весами рёбер, ячейки, соответствующие вершинам, до которых нет пути из начальной, после работы алгоритма могут содержать не только значение Inf, но так же и меньшее число. Но в любом случае, конечное значение такой ячейки не может быть менее Inf - MinW * (MaxN - 1), где MinW - модуль минимально возможного веса ребра, а MaxN - максимальное количество вершин. Если конечное значение ячейки превышает это значение, значит пути до соответствующей вершины не существует. Однако не стоит забывать, что если Inf <= (MinW + MaxW) * (MaxN - 1), то мы не можем рассуждать подобным образом - бесконечность выбрана слишком маленькая.
Алгоритм Форда-Беллмана имеет несколько замечательных особенностей. Во-первых, обратите внимание на то, что при рассмотрении рёбер графа (строка 5), мы рассматриваем сразу все рёбра, нас не интересуют выходящие из какой-либо конкретной вершины. Отсюда следует, что список рёбер, представленный массивом R вовсе не обязан быть упорядочен, как того требовал, например, алгоритм поиска в глубину. Действительно, мы нигде не используем массив указателей G.
Во-вторых, допустим, нам не известно, содержит ли данный граф циклы отриицательного веса. Тогда мы можем сделать хитрую хитрость и определить это. Нам потребуется всего лишь после окончания работы алгоритма произвести ещё одну его итерацию и посмотреть, изменились ли значения массива D. Если да, то это значит, что мы смогли улучшить полученный окончательный результат, т.е. алгоритм отработал неправильно, следовательно, в графе были циклы отрицательного веса. Реализация этой проверки может выглядеть так (истинность наличия таких циклов возвращается в переменной Found: Boolean):
|
7 8 9 10 11 12 |
Found := False; For J := 1 to M do If D[R[J].B] > D[R[J].A] + R[J].C Then Begin Found := True; Break; End; |
В этом примере мы не совсем делаем то, что было написано. Мы не производим ещё одну итерацию и не проверяем изменения значений массива D. Мы просто перебираем все рёбра (строка 8) и смотрим, может ли ещё какая-либо релаксация изменить значения массива (строка 9). Если это так, мы заканчиваем проверку с положительным результатом (строки 10-11). Если ни одна релаксация не меняет текущего состояния массива, то результат остаётся отрицательным, т.к. это значение было ему присвоено перед циклом в строке 7.