嘿，我一直在研究“单源最短路径”问题的贝尔曼福特算法。
现在我被困在一个点上，我需要找出具有负权重循环的图形的解决方案。
但是贝尔曼福特算法在这里不起作用。
有人可以建议我该怎么做。如何解决负重循环的问题？
谢谢你的时间。
问问题
427 次
1 回答
1
如果有一个从原点可以到达的负循环，Bellman-Ford 可以检测到，那么你有两个选择：要么允许重复边，要么不允许。如果你允许重复边，你的最短路径可以被认为是无限负的。否则，如果您不这样做，则问题是NP完全的。来自维基百科：
最短路径问题的一个 NP-Complete 变体要求 G 中的最短路径（包含负循环），使得不重复边。
于 2012-05-16T16:11:47.820 回答