Метод Форда - Беллмана

Данный метод обеспечивает нахождение кратчайших путей m[ s, x_i ] между источником s и всеми другими вершинами x_i Î X \ s для ориентированного графа G = (X, U), в котором отсутствуют контуры суммарной отрицательной длины. Веса дуг l (x_i, x_j) могут иметь любые значения. Метод является итерационным и основан на изменении пометок вершин графа, причем значения (x_i) в конце k -й итерации равны длинам таких кратчайших путей m[ s, x_j ], которые содержат не более k + 1 дуг.

Ниже приводится формальная схема алгоритма, реализующая метод Форда - Беллмана.

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

Данные: орграф G = (X, U), имеющий n вершин, с выделенным иcточником s Î X; веса дуг l (x_i, x_j) для всех (x_i, x_j) Î U.

Результаты: длины l^*(x_i) кратчайших путей m[ s, x_i ] для всех x_i Î X \ s.

Шаг 1 (присвоение начальных значений)

Установить номер итерации k = 0. Определить множество вершин
S = Г(s). Присвоить начальные значения пометкам:

Шаг 2 (обновление пометок вершин)

Для каждой вершины x_j ÎГ(S) изменить пометку:

,

где .

Пометки вершин x_j Ï Г(S) не изменять и присвоить

.

Шаг 3 (проверка условий окончания)

а) Если k £ n - 1 и для всех x_i Î X, то получен оптимальный результат , i = . Конец алгоритма.

б) Если k < n - 1 и хотя бы для одной вершины
x_i Î X, то выполнить переход к шагу 4.

в) Если k = n - 1 и для некоторой x_i Î X, то в графе G существует цикл суммарной отрицательной длины и задача не имеет решения. Конец алгоритма.

Шаг 4 (подготовка к следующей итерации)

Определить множество S следующим образом:

.

Изменить номер итерации k = k + 1 и выполнить переход к шагу 2.

Следует отметить, что на шаге 2 множество S содержит все вершины x_i графа, для которых кратчайшие пути m[ s, x_i ] состоят из k дуг. Множество T_j определяет вершины из множества S, связанные дугами с x_j. Если
x_j Ï Г(S), то кратчайший путь из s в x_j не может состоять из k + 1 дуг и поэтому пометки таких вершин l(x_j) изменять не требуется. На шаге 4 новое множество S содержит все вершины, кратчайшие пути до которых содержат k + 1 дуг.

Представленный алгоритм обеспечивает получение оптимального решения. Доказательство приводится в работах [6, 10] и базируется на принципах динамического программирования и том факте, что если не существует никакого оптимального пути из k дуг, то не может также существовать никакого оптимального пути, содержащего k + 1 дуг.

Вычислительная сложность метода Форда - Беллмана имеет оценку О (n ³), т. е. в случае полного связного графа с n вершинами требуется порядка n ³ операций сложения и сравнения. Алгоритм 1.1 можно использовать и в случае неотрицательных весов дуг, но более предпочтительным является применение алгоритма Дейкстры, так как его оценка трудоемкости составляет О (n ²) операций.

Пример 1.1. Применение метода Форда - Беллмана для графа G = (X, U), приведенного на рис. 1.2 и заданного матрицей D (см. упражнение 1.12), показано в табл. 1.2. Предполагается, что источником s является вершина x ₁. Окончательные значения пометок l^*(x_i) равны 0, 1, 4, 3, -1 для вершин x_i, , соответственно. Кратчайшие пути m[ s, x_i ], где s = x ₁ и , получены с использованием соотношения (1.2). Результаты решения задачи, включая дерево кратчайших путей, представлены на рис. 1.3.

Рис. 1.2. Представление графа для примера 1.1

У П Р А Ж Н Е Н И Я

1.15. Определить особенности графовых моделей, для которых может применяться метод Форда - Беллмана.

1.16. Какое наибольшее число итераций может потребоваться при работе алгоритма 1.1? Изменится ли это значение, если веса всех дуг графа будут неотрицательными?

1.17. Решить задачу построения кратчайших путей m[ x ₂, x ₅] и m[ x ₅, x ₂] для графа, показанного на рис. 1.2.

1.18. Разработать подпрограммы формирования множеств S, Г(S) и T_j для x_j Î Г(S).

1.19. Разработать подпрограммы вычисления меток вершин и проверки условий окончания итерационного процесса для метода Форда -Беллмана.

1.20. Модифицировать алгоритм 1.1 таким образом, чтобы для построения кратчайших путей использовать пометки вида [l^*(x_j), m_j ], описанные в предыдущем разделе.

Таблица 1.2

Результаты работы алгоритма Форда - Беллмана (пример 1.1)

1.21. Решить задачу из примера 1.1 по алгоритму, полученному при выполнении упражнения 1.20.

1.22. Составить программы поиска кратчайших путей по методу Форда - Беллмана для двух способов построения путей (см. раздел 1.2).

Рис. 1.3. Результаты поиска путей (пример 1.1)

1.23. Получить (машинное) решение задачи вычисления длин кратчайших путей m[ x ₁, x_j ], , для графа, показанного на рис. 1.4.

Ответ: вектор значений l^*(x_i), , имеет следующий вид:

(0, -3, -11, -5, 2, -7, -1, 13, 16).

Рис. 1.4. Представление графа для упражнения 1.23