Арбитражная торговля (Алгоритм Беллмана — Форда)

А если надо искать кратчайший путь много раз, можно запускать ФБ только один раз, а потом использовать Дейкстру.

Можна модифицировать алгоритм Дейкстры, таким образом, чтобы он корректно работал с рёбрами отрицательного веса. Сложность алгоритма не поменяется.

Идея — использовать потенциалы Джонсона, то-есть изменить веса ребер таким образом, что бы они стали положительными. Сделать это достаточно просто.

Давайте, просто возьмем и присвоим вершинам графа числа p(v) = кратчайшее расстояние от s к v И будем решать задачу для графа с измененными весами ребер: С'(uv) = C(uv)+p(u)-p(v).

Доказательство состоит из двух лемм:
Л1. Веса всех ребер неотрицательны.
Док-во: пусть существует ребро (uv) вес которого отрицателен, тогда C(uv)+p(u)-p(v)<0, а значит C(uv)+p(u)<p(v), но тогда мы должны были пойти из u в v, и это было бы выгоднее. Противоречие.

Л2. Для любой пары вершин кратчайший пути сохранился.
В самом деле, давайте распишем новую стоимость пути из s в t: C'(s,a1)+C'(a1,a2)+...+C'(ax,t) = C(s,a1)+...+C(ax,t)+(p(s)+...p(ax))-(p(a1)+...+p(t))=oldpath + p(s)-p(t) = oldpath + const.

Называется это все, алгоритмом Джонсона.