Для поиска кратчайших путей на графах с отрицательными весами применяют, например, следующие алгоритмы:

• Алгоритм Джонсона. 1 Находит кратчайший путь между всеми парами вершин во взвешенном ориентированном графе с отрицательными весами без негативных контуров. 1 Идея алгоритма — сформировать на основе исходного графа новый граф без отрицательных дуг, а затем пропустить полученный граф через алгоритм Дейкстры. 1
• Алгоритм Беллмана — Форда. 2 Находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе, при этом вес рёбер может быть отрицательным. 2 Алгоритм представляет собой несколько фаз, на каждой из которых просматриваются все рёбра графа и производится релаксация стоимости вдоль каждого ребра. 2
• Алгоритм Флойда — Уоршелла. 1 Решает задачу полным перебором, перебирает все возможные варианты построения путей. 1 Суть алгоритма в постоянном «релаксировании» длины маршрута: на каждой итерации пробуют попасть из одной вершины в другую через промежуточную вершину, и если этот путь короче, то запоминают уменьшенную длину. 1