Алгоритм Форда-Беллмана — это алгоритм поиска кратчайшего пути во взвешенном графе.
Введение
Предположим, есть ориентированный взвешенный граф G, который имеет n вершин и m рёбер, и определена некая вершина v. Необходимо определить длины самых коротких путей от вершины v до каждой другой вершины. Данный алгоритм может применяться и к графам, которые имеют рёбра с отрицательным весом, что отличает его от алгоритма Дейкстра. Хотя, когда у графа имеются отрицательные циклы, то, естественно, самого короткого пути к отдельным вершинам может и не быть (это объясняется тем, что тогда кратчайший путь будет иметь бесконечный вес со знаком минус). Правда, есть возможность модификации данного алгоритма, и тогда он будет давать сообщение о присутствии цикла, имеющего отрицательный вес, или, более того, выводить данный цикл.
Алгоритм назван в честь учёных из США Ричарда Беллмана и Лестера Форда. Изобретателем основ этого алгоритма по факту является Форд, который вывел его в середине прошлого века при работе с иной математической задачей, в одной из подзадач которой нужно было определить самый короткий путь в графе. Тогда Форд сделал эскиз алгоритма решения такой задачи. А чуть позже Беллман выпустил статью, которая была посвящена именно проблеме определения наикратчайшего пути. В своей работе он дал чёткую и однозначную формулировку алгоритма, и она актуальна и по сей день.
Алгоритм Форда-Беллмана
Предполагается, что граф не имеет циклов с отрицательным весом. Зададим массив расстояний d[0…n – 1], который по завершению выполнения алгоритма содержит итоговый результат. Сначала заполним массив такими данными: d[v] = 0, а другие элементы d[] будут определены как имеющие размер бесконечность. Непосредственно алгоритм Форда-Беллмана состоит из нескольких фаз. Во всех фазах выполняется просмотр всех рёбер графа, и согласно алгоритма делается попытка релаксации (rеlax, ослабления) по направлению каждого ребра (а, b) стоимости с. Релаксация вдоль ребра означает попытку улучшения значения d[b] за счёт значения d[а] + с. По факту это означает попытку улучшения результата для вершины b, используя ребро (а, b) и действующий ответ для вершины a. Заявлено, что хватит n – 1 фазы алгоритма для правильного подсчёта длин всех самых коротких путей в графе (конечно, без циклов с отрицательным весом). Если вершины являются недостижимыми, то дистанция d [] для них так и остаётся бесконечной.
Простая реализация алгоритма
В алгоритме Форда-Беллмана удобнее представить граф как один список всех рёбер, а не n штук, как делается в некоторых других алгоритмах графов. В программе, представленной ниже, определяется структура данных edge для рёбер. В качестве входных данных алгоритма выступают числа n, m, списки рёбер e, а также нумерация вершины старта v. Нумерация вершин идёт от нуля до n – 1. INF — это обозначение константы с размерностью «бесконечность». Она должна быть подобрана так, чтобы всегда была больше всех вероятных длин путей.
Рисунок 1. Простая реализация алгоритма. Автор24 — интернет-биржа студенческих работ
Выполнение проверки "if (d[e[j].a]
Улучшенная реализация алгоритма
Работу алгоритма возможно сделать более быстрой. Часто итоговый результат может быть найден лишь за незначительное число фаз, а остальные фазы работы алгоритма по сути бесполезны и в них в холостую ведётся просмотр остальных рёбер. По этой причине надо сохранять флаг наличия изменений в данной, работающей фазе, и если появилась фаза где нет изменений, то работу алгоритма можно прекращать. Такая модификация существенно ускорит работу алгоритма, особенно при случайных графах. И так же при этой оптимизации нет необходимости контролировать количество фаз алгоритма, его работа прекратится автоматически через необходимое количество фаз.
Рисунок 2. Улучшенная реализация алгоритма. Автор24 — интернет-биржа студенческих работ
Восстановить пути
Работу алгоритма Форда-Беллмана возможно преобразовать таким образом, что он будет находить самые короткие маршруты, и, кроме того, выводить и показывать эти самые короткие маршруты. С этой целью создадим добавочный массив р[0…n – 1], который будет служить для сохранения истории, то есть предыдущую вершину в самом коротком маршруте, который ведёт к ней. То есть, самый короткий путь к какой-либо вершине а будет самым коротким маршрутом до какой-либо вершины р[a], к которому добавили в окончание вершину а. Следует отметить, что действие алгоритма Форда-Беллмана следует этой же логической цепи. Алгоритм, полагая, что самый короткий маршрут до одной вершины уже вычислен, делает попытку уменьшить (улучшить) самый короткий маршрут до следующей вершины. Таким образом, при улучшении необходимо просто сохранить в массиве р [], какая вершина вызвала это улучшение.
Вначале выполняется проход по ранее пройденным вершинам, с началом в вершине t, и весь маршрут сохраняется в переменной path. В этой переменной (списке) и будет самый короткий путь.
Доказательство алгоритма
Следует отметить, что алгоритм Форда-Беллмана способен определить маршруты ко всем вершинам, которые возможно достичь, а релаксацию оставшихся вершин он выполнять вообще не будет. Можно доказать, что, когда будут исполнены i фаз алгоритма, будут правильно определены все оптимальные маршруты, которые по длине (по количеству рёбер) не будут превосходить i. Или по-другому, для каждой вершины а будем считать, что К это количество рёбер в самом коротком маршруте к ней. То есть это означает, что после К фаз самый короткий маршрут будет с гарантией определён.
