确定两个节点之间的路径时没有负循环

Question

为什么有向加权图不能包含负权重的循环，如果我们想确定该图的两个节点之间的最短路径？

Answer 1

因为如果有这样一个循环，对于每个你可能想到的"shortest path"，我可以通过简单地再次穿越这个负循环来选择一个更好的。这肯定会降低整体路径成本，因为假设这个循环是负权重。

Answer 2

因为"shortest"实际上意味着"least cost/weight"路径。

通过负权重循环，可以使用它来获得任意低的 ny 路径（包含此循环）的权重。

Answer 3

因为如果是的话，最短路径可以是-inf.

想象一下这个例子，你想要计算 A 和 D 之间的最短路径。可能你希望它是 A - B - D，6 步。但是您可以根据需要多次循环 B - C - B 循环。那么，最短路径就是A - B - C - B - C - ... - B - C - B - D.

Answer 4

因为负循环会以下列方式影响路径权重：

a----------b-----------c---------------d
     2     |     2     |       4
           |           |
           | -3        | -3
           |           |
           e-----------f
                 2

第一次尝试寻找路径：

a->b->c->d cost = 8

现在让我们进入循环：

a->b->c->f->e->b->c->d cost = 8 + (-2)

嗯，便宜了两倍，但我们可以做得更好：

a->b->c->(f->e->b->c)^i->d cost = 8 + (-2) ^ i

明显的问题：每运行通过循环，路径变得更便宜，我们最终以无限循环作为最短路径。

但这并不适用于所有寻路算法。例如，Bellman-Ford-algorithm 能够处理下降沿，但代价是效率较低。

确定两个节点之间的路径时没有负循环

No negative cycles when determining path between two nodes

algorithm

graph

shortest-path