我有一个边权为负的有向图。图形被程序修改，有时会形成负循环。当这种情况发生时，最短路径算法(Bellman-ford/Johnson/Floyd-Warshall)会检测到这种负循环的存在并失败，但不会产生其他有用的信息。
我想确定哪条边导致负循环，并禁止在图中进行此类修改。有人能帮我拿个指针吗?
谢谢,保罗
Paul，如果你要添加一条边(源，目标，权重)，并且你知道从目标到源的距离，那么当且仅当新权重+旧距离为负时，你正在创建一个负循环。
另一方面，如果你有一个图，bellman-ford算法检测负循环，当它找到一个时可以显示一个。你只需要找到一个实现(而不是失败)，或者自己写一个。这不是一个很难的算法，而且网络上有很多伪代码。
(如果你想为你定制一个，可能需要几天的咨询工作。我以这类事情为生，我很乐意这样做。
我不确定你到底需要什么。我不知道，但我可以想象有一个在线版本的Bellman-Ford，它可以在新边加入时廉价地保持距离，如果你添加了一个不好的边，它会尖叫。