嘿，我一直在研究贝尔曼福特算法的"单源最短路径"问题。
现在我被困在需要找到具有负权重周期的图形的解决方案的一点上。
但是贝尔曼福特算法在这里不起作用。
有人可以建议我该怎么做。如何解决负体重周期的问题？
谢谢你的时间。
如果存在
可以从原点到达的负循环，Bellman-Ford 可以检测到，那么您有两种选择：要么允许重复边，要么不允许。 如果允许重复边，则最短路径可能被视为无限负。 否则，如果不这样做，则问题为 NP 完成。 来自维基百科：
最短路径问题的一个NP-Complete变体要求G中的最短路径（包含负循环），以便不重复边。
在这里讨论的一篇论文中，作者（Wulff-Nilson，Nanongki，Berstein）提到，具有负权重循环的图可以简化为没有这种循环的图，然后他们给出了一种在近乎线性时间内找到最短路径的方法。