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

Алгоритмы   7 января 2012  Автор статьи:  

Задан ориентированный взвешенный граф, содержащий, возможно, дуги отрицательного веса. Необходимо найти веса кратчайших путей от вершины v до всех остальных вершин.

Алгоритм решения

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

Пусть N – количество вершин графа, M – количество дуг, l_{i,j} – вес дуги, ведущей из вершины i в вершину j. Обозначим за T_{i,j}  вес кратчайшего пути из v в j, который содержит не более i дуг. В случае отсутствия такого пути положим T_{i,j}=\infty, где бесконечность – это некоторое значение, заведомо превосходящее все возможные расстояния. При i=0  существует единственный допустимый путь – путь из вершины v в неё саму, имеющий нулевой вес. Соответственно, при j\ne v T_{j,0}=\infty. Пусть теперь i>0. Понятно, что кратчайший путь из вершины v в вершину j состоит из кратчайшего пути из v в некоторую вершину p и дуги (p,j). Тогда можно записать следующие рекуррентные соотношения:

T_{i,j}=\begin{cases}0 ,\text{ if }i=0,\,j=v; \\\infty,\text{ if }i=0,\,j\ne v; \\\min(\infty\min{k \in V,\,(k,j)\in E,\,T_{i-1,k}<\infty}(T_{i-1,k}+l_{k,j})),\text{ if }i>0.\\\end{cases}

Здесь V — множество вершин графа, E — множество дуг.

Отметим, что оптимальный путь не должен содержать циклов. В самом деле, если у нас есть некоторый путь с циклом, то, выбросив цикл, мы получим путь меньшего либо равного веса. Тогда максимальное количество дуг в пути будет равно N-1 (в противном случае в пути появится цикл).

Если реализовывать алгоритм непосредственно по приведённым выше соотношениям, то его сложность составит O(N^2M). Попробуем улучшить эту оценку. Заметим, что для каждой дуги можно однозначно определить, при решении подзадач для какой именно вершины она будет использована. Тогда, вместо того чтобы при каждом i перебирать все вершины и для каждой из них все рёбра, можно просто перебрать все рёбра. Получаем асимптотическую сложность O(NM).

Кроме того, нет смысла хранить всю матрицу весов кратчайших путей. Достаточно лишь двух её последних строк. Если же мы немного отойдём от составленных рекуррентных соотношений, то сможем обойтись всего одной строкой. В самом деле, будем брать веса вспомогательных путей из некоторой строки и записывать улучшенные значения в неё же. Тогда после завершения i-ой итерации могут быть найдены веса оптимальных путей, содержащих более чем i дуг, однако все кратчайшие пути, содержащие t дуг, гарантированно будут найдены после выполнения t-ой итерации (действительно, они либо будут найдены на t-ой итерации в соответствии с рекуррентными соотношениями, либо ранее).

Предположим, что нам необходимо вывести также сам кратчайший путь. Тогда для каждой подзадачи необходимо будет сохранять предпоследнюю вершину в пути, т.е. значение k (см. рекуррентное соотношение). Это значит, что понадобится матрица размерности NM.

Итак, если все циклы в графе имеют неотрицательный вес, то для нахождения весов кратчайших путей будет достаточно N-1 итерации. Но в противном случае ситуация изменится. Если в пути есть цикл отрицательного веса, то мы можем двигаться по нему бесконечно долго, каждый раз уменьшая длину пути. Произведём тестовую N-ую итерацию. Если после неё изменились какие-то из ранее вычисленных расстояний, то это равносильно тому, что в графе есть цикл отрицательного веса.

Алгоритм носит имя двух американских учёных: Ричарда Беллмана и Лестера Форда. Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой задачи. Беллман в 1958 г. опубликовал статью, в которой алгоритм был сформулирован в том виде, в котором он известен нам сейчас.

Автор статьи – Сухов Сергей

Научиться программировать

  • на Delphi

  • на Java

  • на C++