Учёт знака весов рёбер важен при поиске кратчайших путей, поскольку при наличии отрицательных весов наиболее короткие пути с малыми весами часто содержат больше рёбер, чем пути с более высокими весами. 5

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

Например, алгоритм Дейкстры работает только с графами, у которых веса всех рёбер положительны, и не способен корректно обработать графы с отрицательными весами рёбер. 1 Алгоритм Беллмана — Форда, в свою очередь, находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе, где вес рёбер может быть отрицательным. 24