如何求负权圈图的单源最短路径

Question

嘿，我一直在研究“单源最短路径”问题的贝尔曼-福特算法。

现在我被困在一个点上，我需要找出一个具有负权重圈的图的解。

但贝尔曼·福特算法在这里不起作用。

有人能建议我怎么做吗？如何解决负权重循环的问题？

耽误您时间，实在对不起。

Answer 1

如果存在一个从原点可达的负循环，贝尔曼-福特可以检测到，那么你有两个选择:允许重复的边，或者不允许。如果你允许重复的边，你的最短路径可以被认为是无限负的。否则，如果不这样做，问题就是NP完全的。来自Wikipedia

最短路径问题的一个NP完全变体要求G中的最短路径(包含负圈)，这样就没有边重复。