Алгоритм Форда-Беллмана
Пусть дан ориентированный взвешенный граф G с n вершинами и m рёбрами, и указана некоторая стартовая вершина v. Требуется найти длины кратчайших путей от вершины v до всех остальных вершин.
Также как и Дейкстра, алгоритм Форда-Беллмана ищет расстояние от 1 вершины до всех остальных, но работает с отрицательными ребрами.
Сам алгоритм Форда-Беллмана представляет из себя несколько фаз (
n-1). На каждой фазе просматриваются все рёбра графа, и алгоритм пытается произвести релаксацию вдоль каждого ребра
(a, b) стоимости
c.
Релаксация вдоль ребра — это попытка улучшить значение
d[a] значением
d[b] + c. Фактически это значит, что мы пытаемся улучшить ответ для вершины , пользуясь ребром и текущим ответом для вершины.
Массив
d - это массив кратчайших длин от стартовой вершины, также как и в Дейкстре, изначально заполняем максимально большими числами, кроме стартовой вершины, в которой надо поставить 0.
Для хранения ребер используется не матрица смежности или весовая матрица, а список, в котором указывается из какого узла выходит ребро (
from), в какое оно приходит (
to) и его вес (
cost).
struct edge {
int from, to, cost;
};
vector<edge> edges;
Константа
INF обозначает число "бесконечность" - её надо подобрать таким образом, чтобы она заведомо превосходила все возможные длины путей.
Простейшая реализация алгоритма:
d[v] = 0;
for (int i=0; i<n-1; ++i)
for (int j=0; j<m; ++j)
if (d[edges[j].from] < INF)
d[edges[j].to] = min (d[edges[j].to], d[edges[j].from] + edges[j].cost);
или немного покороче с использованием синтаксиса
С++11:
d[v] = 0;
for (int i=0; i< n-1; ++i)
for (edge j: edges)
if (d[j.from] < INF)
d[j.to] = min (d[j.to], d[j.from] + j.cost);
Пример работы
Возьмем простой ориентированный граф с 5-ю узлами, 4-мя ребрами с весом равным 1.
Введем список ребер именно в таком порядке.
4 5 1
3 4 1
2 3 1
1 2 1
Исходные значения в массиве кратчайших длин:
где inf - это должно быть такое подобранное целое число, которое бы всегда было больше веса ребра.
После 1-го прохода
После 2-го прохода
После 3-го прохода
После 4-го прохода
Если бы мы подавали ребра в порядке от 1 до последнего, то могли бы найти кратчайшие длины уже после 1-го прохода.
