我有一个带有负边权重的有向图。图形被程序修改，有时会形成负循环。当这种情况发生时，最短路径算法（Bellman-ford/Johnson/Floyd-Warshall）会检测到这种负循环的存在并失败，但不会产生其他有用的信息。
我想确定是什么边导致了负循环，并不允许在图中进行此类修改。有人可以帮我指点吗？
谢谢，
保罗
问问题
463 次
1 回答
0
Paul，如果您要添加一条边（源、目的地、权重），并且您知道从目的地到源的距离，那么当且仅当新权重 + 旧距离为负时，您将创建一个负循环。
另一方面，如果你刚刚得到一个图，bellman-ford 算法会检测负循环，并在找到负循环时展示一个。您只需要找到一个可以做到这一点的实现（而不仅仅是失败），或者自己编写一个。这不是一个困难的算法，网上有很多伪代码。
（如果你想要一个为你定制的，这可能需要几天的咨询工作。我做这种事情是为了谋生，我很乐意这样做。）
我不确定你到底需要什么。我不知道，但我想有一个 Bellman-Ford 的在线版本，它可以在新边缘出现时以便宜的价格保持最新的距离，如果你添加一个不好的边缘，它会尖叫。
于 2013-09-24T18:41:06.583 回答