最短路径：识别导致负循环的边
我有一个带有负边权重的有向图。图形被程序修改，有时会形成负循环。当这种情况发生时，最短路径算法（Bellman-ford/Johnson/Floyd-Warshall）将检测到这种负循环的存在并失败，但不会产生其他有用的信息。
我想确定什么边缘导致负循环并禁止在图中进行此类修改。有人可以帮我指点一下吗？
谢谢，
保罗
I have a directed graph with negative edge weights. The graph is modified by the program and sometimes will form negative cycles. When that happens, shortest path algorithms (Bellman-ford/Johnson/Floyd-Warshall) would detect the existence of such negative cycle and fail, but no other useful information is produced.
I would like to identify what edge causes the negative cycle and disallow such modifications in the graph. Can someone help me with a pointer?
Thanks,
Paul
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Paul，如果您要添加一条边（源、目的地、权重），并且您知道从目的地到源的距离，那么当且仅当新权重 + 旧距离为负时，您才会创建负循环。
另一方面，如果您刚刚得到一个图表，贝尔曼福特算法会检测负循环，并在找到负循环时显示一个。您只需要找到一种可以实现这一点的实现（而不仅仅是失败），或者自己编写一个实现。这不是一个困难的算法，网上有很多伪代码。
（如果您想要为您定制一份，这可能需要几天的咨询工作。我以做这种事情为生，并且很乐意这样做。）
我不确定您到底需要什么。我不知道，但我想象有一个贝尔曼-福特的在线版本，当新的边缘出现时，它可以便宜地保持最新的距离，如果你添加一个坏的边缘，它会尖叫。
Paul, If you're about to add an edge (source, destination, weight), and you know the distance from destination to source, then you're creating a negative cycle if and only if new weight + old distance is negative.
On the other hand, if you've just got a graph, the bellman-ford algorithm detects negative cycles and can exhibit one when it finds one. You just need to either find an implementation that does that (rather than just failing), or write one yourself. It's not a difficult algorithm and there's lots of pseudocode on the web.
(It's probably a couple of days consultancy work if you want one custom-written for you. I do this sort of thing for a living and would be happy to.)
I'm not sure exactly what you need. I don't know, but I'd imagine that there's an on-line version of Bellman-Ford that keeps its distances up to date cheaply as new edges come in, and will scream if you add a bad one.