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

Алгоритм Дейкстры предполагает, что добавление новых рёбер всегда увеличивает длину пути. 3 При наличии отрицательных весов алгоритм может зациклиться или выдать неверный результат, так как он основан на предположении, что, пройдя по ребру, нельзя уменьшить общее расстояние. 4

Алгоритм Беллмана-Форда, в отличие от Дейкстры, способен работать с графами, имеющими рёбра с отрицательными весами. 8 Более того, он позволяет определить, есть ли в графе цикл отрицательного веса (цикл, сумма весов рёбер которого отрицательна). 3 Наличие такого цикла означает, что не существует кратчайшего пути, так как можно бесконечно «наматывать» круги по этому циклу, каждый раз уменьшая длину пути. 3