Dijkstra 算法的负边缘

Question

谁能帮我解决这个问题
我仍然对 Dijkstra 算法是否适用于负边感到困惑
这个问题来自 Grokking Algorithms 一书，在它的勘误表中据说这个问题有一个可能的答案
它怎么可能有负边的答案？

Answer 1

首先，Dijkstra 算法不适用于所有负权重图，但在这种特殊情况下，您可以看到负权重在从起点到任何其他点的最短路径上没有任何不同在图上。这就是为什么不管有没有负边沿你都会得到相同的结果。

为什么 Dijkstra 在负加权图上不起作用的想法在这里得到了很好的解释（感谢 Amit）-> Why doesn't Dijkstra's algorithm work for negative weight edges?

Answer 2

自从我上次接触与 Dijkstra 相关的任何东西以来已经过去了 10 年，但我认为这个不会中断，因为每次你越过负数部分时，循环仍然会增加总和（负 1 与数）加上 2)。这样，带有负数的路径就被丢弃了。但是把那个负 1 改成负 5 然后你就有问题了。

我现在不在我的电脑上将这张图表应用到我 10 年前的作业中，但我很确定这就是正在发生的事情。