Я не уверен, что вопрос, но здесь идет ...
Классическая реализация алгоритма Дейкстры может обрабатывать только положительные веса ребер, но есть способ заставить его работать с отрицательными затратами ребер. Всякий раз, когда вы обновляете узел, поместите обновленный узел обратно в очередь. Тем не менее, это спорно, является ли это на самом деле Дейкстр или Беллман-Форд с приоритетной очередью.
Например, рассмотрим этот график:
1 - 2 (100)
2 - 3 (-200)
1 - 3 (50)
3 - 4 (100)
Классическая Дейкстра установит D [1] = 0, D [2] = 100, D [3] = 50, D [4] = 150, D [3] = -100 и остановится. Однако при установке D [3] = -100 добавьте 3 обратно в очередь и продолжите алгоритм. Это даст D [4] = 0, что правильно. Однако я не уверен, считается ли это «алгоритмом Дейкстры».
Что касается Беллмана-Форда, график не обязательно должен быть направленным, и (циклы отрицательной стоимости, другие циклы в любом случае не имеют значения) могут существовать, просто убедитесь, что вы обнаруживаете циклы. Цикл обнаруживается при извлечении узла из очереди n раз, где n - количество узлов. Вы можете сделать ту же проверку, чтобы обнаружить цикл в «модифицированном алгоритме Дейкстры», который я описал выше.
Floyd Warshall - стоимость в кубических числах узлов. Неэффективно для всего, кроме очень маленьких графиков. Предполагается, что циклы отрицательной стоимости отсутствуют, но вы можете использовать его для обнаружения таких циклов, см. wikipedia .
MST - использовать Крускала, когда число ребер ближе к O (n), чем к O (n 2 ). В противном случае используйте Prim. Оба будут работать на графиках любого типа, даже если они содержат отрицательные веса ребер и циклы.
Еще один алгоритм кратчайших путей, который мне лично очень нравится, это Алгоритм набора . Мне нравится думать об этом, как считать сортировку на графиках. Также прочитайте этот довольно исчерпывающий документ .