Пусть $G = (V, E)$ – ориентированный граф и $w: E → R_+$ — функция длин ребер G. Длиной ребра $e$ называется значение $w(e)$. Длиной пути $p = (v_0, v_1, … , v_k)$ называется сумма $w(p) = ∑ w(v_{i-1}, v_i)$ длин ребер, входящих в $p$. Длиной кратчайшего пути из $u$ в $v$ называется: $δ(u, v) = min \{ w(p)\ |\ p = (u, …, v)$ путь в графе $G$ }

• считаем минимум пустого множества $min\ \emptyset = \infin$

Кратчайшим путём из $u$ в $v$ называется путь из $u$ в $v$, для которого $w(p) = δ(u, v)$. Кратчайших путей может быть несколько.

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

Вычисление кратчайших путей в графе c ребрами и/или циклами отрицательной длины за с операций $O(|V| × |E|)$

(оценка такая потому что мы повторяем цикл V-1 раз и на каждом шаге идём по всем рёбрам, а потом ещё раз чтобы проверить на отриц. цикл) Формально: Инициализация занимает Θ(V) времени, каждый из |V|−1 проходов требует Θ(E) времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает O(E) времени. Значит алгоритм Беллмана-Форда работает за O(VE) времени.

Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем. В то же время сложность его равна $O(|V| × |E|)$ , что больше, чем показатель для алгоритма Дейкстры.

Входные данные:

• Граф и начальная вершина src

Выходные данные:

• Кратчайшее расстояние до всех вершин от src. Если попадается цикл отрицательного веса, то самые короткие расстояния не вычисляются, выводится сообщение о наличии такого цикла.

1. На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src], где src — исходная вершина.

2. Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V|-1 раз, где |V| — число вершин в данном графе.

   • Произведите следующее действие для каждого ребра : Если dist[v] > dist[u] + вес ребра uv, то обновите dist[v]

     dist [v] = dist [u] + вес ребра uv

3. На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра необходимо выполнить следующее:

   • Если dist[v] > dist[u] + вес ребра uv, то в графе присутствует цикл отрицательного веса.

Идея шага 3 заключается в том, что шаг 2 гарантирует кратчайшее расстояние, если граф не содержит цикла отрицательного веса. Если мы снова переберем все ребра и получим более короткий путь для любой из вершин, это будет сигналом присутствия цикла отрицательного веса.

How does this work? Like other Dynamic Programming Problems, the algorithm calculates shortest paths in a bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on. After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edges

/* Вычисляем длины кратчайших путей от источника до вершин графа в порядке увеличения числа ребер в пути */ $d_{min}[s] = 0$, $d_{min}[v] = \infin$ для $v != s$ Для i = 1, …, |V|-1 // кратчайшем пути <= |V|-1 ребер Для каждой вершины v dnext[v] = min { dmin[v], dmin[u]+w(u,v) } dmin = dnext // обычно значение min{…} записывают сразу в dmin Если dmin[u]+w(u,v) < dmin[v] для одного из ребер (u, v), то G содержит цикл отрицательной длины