Djikstra的算法是否不修改封闭顶点的距离？

Question

我记得曾经读过Djiktra的算法将一个节点标记为已访问，但它不会再次更新其距离。考虑下图：

A-3-B-7-F
|       |
8     -3
|    /
C-3-E

该算法将进入A-> B-> C，并且E和F将排队。但是F将被优先选择，因为它的距离更短。然后，将选择E并修改F的距离。在这种情况下，访问F后不对F进行修改吗？

Answer 1

您的图形的边缘权重为负-3。

Dijkstra的算法在存在负边缘权重时不起作用。您在问题中给出的图形就是一个足以证明这一事实的例子。

来自Wikipedia：

与Dijkstra的算法不同，Bellman–Ford algorithm可以用于具有负边缘权重的图，只要该图不包含从源顶点可到达的negative cycle。