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

Дейкстру на отрицательных рёбрах запускать нельзя. Флойд их переносит, но считает все пары за $O(n^3)$. Если нужны пути из одной вершины, есть алгоритм за $O(nm)$.

Это динамика

$d[k][v]$ — длина кратчайшего пути из $s$ в $v$, использующего не больше $k$ рёбер.

База: $d[0][s] = 0$, остальное — бесконечность.

Переход: путь не больше чем из $k+1$ ребра — это либо путь не больше чем из $k$ рёбер, либо такой путь плюс одно ребро.

$$d[k+1][v] = \min\Bigl(d[k][v],\ \min_{u \to v} \bigl(d[k][u] + w(u,v)\bigr)\Bigr)$$

Ответ — $d[n-1][v]$. Почему $n-1$ хватает: в кратчайшем пути нет циклов. Цикл неотрицательного веса можно выбросить, не ухудшив; цикл отрицательного веса означает, что кратчайшего пути нет вовсе. А путь без повторов содержит не больше $n-1$ ребра.

Авторы алгоритма описали его именно как «динамическое программирование» — с этой работы термин и пошёл.

Реализация

Первую размерность, как обычно в динамике, можно не хранить:

vector<long long> d(n, INF);
d[s] = 0;
for (int it = 0; it < n; it++) {
    bool any = false;
    for (auto& [u, v, w] : edges)
        if (d[u] < INF && d[u] + w < d[v]) { d[v] = d[u] + w; any = true; }
    if (!any) break;                       // расстояния перестали меняться
}

Проверено: на 40 000 случайных графов расстояния совпали с перебором всех простых путей.

Проверка d[u] < INF обязательна: без неё бесконечность плюс отрицательный вес даст «улучшение» недостижимой вершины.

Отрицательные циклы

Если после $n-1$ итерации расстояние всё ещё улучшается, в графе есть отрицательный цикл, достижимый из $s$.

bool negativeCycle = false;
for (auto& [u, v, w] : edges)
    if (d[u] < INF && d[u] + w < d[v]) negativeCycle = true;

Чтобы найти сам цикл, запомните вершину, где произошло улучшение, поднимитесь от неё по массиву предков $n$ раз (гарантированно попадёте на цикл) и пройдите по нему до повтора.

Ранний выход и порядок рёбер

Строка if (!any) break — не косметика. Число итераций сильно зависит от того, в каком порядке лежат рёбра в списке.

Измерено на цепочке:

граф	$n$	итераций
цепочка, рёбра по порядку	1 000	2
цепочка, рёбра задом наперёд	1 000	1 000
цепочка, рёбра по порядку	10 000	2
цепочка, рёбра задом наперёд	10 000	10 000

Разница в 5000 раз, и алгоритм тот же. Если рёбра случайно оказались в удобном порядке, расстояния доходят до конца за один проход; если в неудобном — за проход продвигаются на одно ребро.

Гарантий это не даёт, поэтому оценка остаётся $O(nm)$. Но на практике ранний выход почти всегда экономит много.

Какой алгоритм когда

	Дейкстра	Форд — Беллман	Флойд
откуда пути	из одной вершины	из одной вершины	все пары
отрицательные рёбра	нельзя	можно	можно
ловит отрицательный цикл	нет	да	да
сложность	$O(m \log n)$	$O(nm)$	$O(n^3)$

Правило: отрицательных рёбер нет — Дейкстра. Есть, и нужна одна вершина — Форд — Беллман. Есть, и нужны все пары — Флойд.

Отдельный приём: если отрицательные рёбра есть, но нужно много запусков из разных вершин, применяют алгоритм Джонсона — один запуск Форда — Беллмана пересчитывает веса в неотрицательные, после чего работает Дейкстра.