data-structures - 如何为具有负权重循环的图获取单源最短路径

Question

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

现在我被困在一个点上，我需要找出具有负权重循环的图形的解决方案。

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

有人可以建议我该怎么做。如何解决负重循环的问题？

谢谢你的时间。

Answer 1

如果有一个从原点可以到达的负循环，Bellman-Ford 可以检测到，那么你有两个选择：要么允许重复边，要么不允许。如果你允许重复边，你的最短路径可以被认为是无限负的。否则，如果您不这样做，则问题是NP完全的。来自维基百科：

最短路径问题的一个 NP-Complete 变体要求 G 中的最短路径（包含负循环），使得不重复边。