Dijkstra的算法是否不修改标记顶点的距离？

Question

我记得阅读过，一旦Dijkstra的算法将节点标记为已访问，它就不会再更新其距离。考虑下图：

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

该算法将访问A→B→C，并且将E和F排队。但是F将被优先选择，因为它的距离更短。然后，将选择E并找到到F的更短距离。在这种情况下，即使已经标记了F的距离也不应修改吗？

Answer 1

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

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

来自Wikipedia：

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