Алгоритм Дейкстры ошибается на отрицательных рёбрах. Два других классических алгоритма закрывают этот пробел: Беллман–Форд (один источник, отрицательные веса допустимы, обнаруживает отрицательные циклы) и Флойд–Уоршелл (кратчайшие пути между всеми парами).
Отрицательное ребро и отрицательный цикл
Ребро с отрицательным весом (прибыль вместо расхода) допустимо, и кратчайшие пути остаются определёнными. Отрицательный цикл — цикл с отрицательной суммой: каждый круг уменьшает путь, поэтому кратчайшего пути не существует (-∞). Хороший алгоритм должен такой цикл обнаружить.
Беллман–Форд
Кратчайший путь без циклов содержит не более V - 1 рёбер. Поэтому достаточно V - 1 раз релаксировать все рёбра: после k-го прохода значения dist верны для всех путей не более чем из k рёбер. Ещё один проход — проверка: если какое-то ребро всё ещё улучшается, из старта достижим отрицательный цикл.
INF = float("inf")