Алгоритм Дейкстры не может работать с отрицательными весами в графе, потому что он предполагает, что добавление ребра к пути делает этот путь более длинным. 4

Однако в графе с отрицательными дугами это не так: например, при запуске алгоритма Дейкстры из вершины А на первом шаге он решит, что уже нашёл кратчайший путь к вершине В, но путь А-Б-В на самом деле короче, чем А-В. 1

Для работы с графами, содержащими рёбра с отрицательным весом, рекомендуется использовать другие алгоритмы, например, Беллмана-Форда. 2

Также можно попробовать исправить ситуацию, найдя наименьший (самый отрицательный) вес ребра и добавив абсолютное значение этого числа ко всем весам рёбер, чтобы получить сеть без отрицательных весов. 4 Однако этот способ не работает, так как кратчайшие пути в новой сети никак не связаны с кратчайшими путями в прежней. 4