В алгоритмах кратчайшего пути важно учитывать отрицательные веса рёбер, потому что при их наличии наиболее короткие пути с малыми весами часто содержат больше рёбер, чем пути с более высокими весами. 1 В случае положительных весов алгоритм ищет пути напрямик, а при наличии отрицательных — обходные, которые содержат столько рёбер с отрицательными весами, сколько можно отыскать. 1

Кроме того, отрицательные веса расширяют применимость задач поиска кратчайших путей в качестве модели для решения других задач. 1

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