Dijkstra 算法不会修改标记顶点的距离吗？
Does Dijkstra's algorithm not modify the distance of a marked vertex?
我记得读过，一旦 Dijkstra 算法将一个节点标记为已访问，它就不会再次更新它的距离。考虑下图：
A-3-B-7-F
| |
8 -3
| /
C-3-E
算法会访问A→B→C，E和F会排队。但是 F 将首先被选中，因为它的距离更小。然后将选择 E 并找到到 F 的更短距离。这样的话，F的距离是不是已经标记好了，难道不应该修改吗？
您的图形具有负边权重 -3。
Dijkstra 算法在边权重为负时不起作用。您在问题中提供的图表足以证明这一事实。
来自Wikipedia：
Unlike Dijkstra's algorithm, the Bellman–Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s.
我记得读过，一旦 Dijkstra 算法将一个节点标记为已访问，它就不会再次更新它的距离。考虑下图：
A-3-B-7-F
| |
8 -3
| /
C-3-E
算法会访问A→B→C，E和F会排队。但是 F 将首先被选中，因为它的距离更小。然后将选择 E 并找到到 F 的更短距离。这样的话，F的距离是不是已经标记好了，难道不应该修改吗？
您的图形具有负边权重 -3。
Dijkstra 算法在边权重为负时不起作用。您在问题中提供的图表足以证明这一事实。
来自Wikipedia：
Unlike Dijkstra's algorithm, the Bellman–Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s.