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

Пусть дан ориентированный взвешенный граф 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

Исходные значения в массиве кратчайших длин:
 
0 inf inf inf inf

где inf - это должно быть такое подобранное целое число, которое бы всегда было больше веса ребра.

после 1-го прохода:
 
0 1 inf inf inf

после 2-го прохода:
 
0 1 2 inf inf

после 3-го прохода:
 
0 1 2 3 inf


после 4-го прохода: 
 
0 1 2 3 4

Если бы мы подавали ребра в порядке от 1 до последнего, то нахождение кратчайших длин может быть и после 1-го прохода.