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

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

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