我正试图理解为什么Bellman-Ford算法不能与负权循环一起工作。我知道负权环会阻止程序给出正确答案。但是如果有负权环，程序中会发生什么呢?
谢谢你的帮助
Bellman-Ford算法查找加权图中从源顶点到所有其他顶点的最短路径。
负权循环的问题是没有最短路径。
不绘图，考虑4个节点的情况，其中A为源，B、C、D节点为其他顶点。
所有边的权值如下:
w(A,B) = 1
w(B,C) = 1
w(C,D) = 1
Bellman-Ford会得出如下最短路径长度
path(A~B) = 1
path(A~C) = 2
path(A~D) = 3
但是如果我们添加一条边，产生一个负权循环呢?例如，从C到B的边的权值为-2。
w(C,B) = -2
现在有一个负权环。通过遍历(B,C,B)，我们得到总路径权值为-1(1 + -2)。
如果我们再次运行Bellman-Ford，它会像之前一样给出它认为的从a到D的最短路径。[注1]
但这一次，它将是错误的。
实际上，算法给出的最短路径权值是多少并不重要，因为总能找到一个更短的
例如，假设算法给了我们3 (A,B,C,D)的原始路径权值。很容易看出，我们可以构造一个更短的路径:(A,B,C,B,C,D)，它给我们的路径权值为2。
但这也不是最短路径。例如，(A,B,C,B,C,B,C,D)给出的路径权值为1。
如你所见，我们可以构造一个任意短的路径权值，通过在顶点B和c之间重复循环。这是正确的，因为我们的图包含一个负权环。
所以不是Bellman-Ford不能正确地找到最短路径。
…更准确地说，不存在最短路径
[1]在Bellman-Ford中检测负权环并不难，所以这里假设了一个简单的实现。