algorithm - Dijkstra算法的一个负边缘失败示例

我试着去想一个所有边都有正权重的图，除了一条边，这样dijkstra的算法就不能产生正确的输出。
我很乐意有个主意。
编辑：
我把这张图看作反例，但我不明白为什么。
顶点A将是最后一个从队列中弹出的，然后我们将Relax()边A->E。因此路径S->A->E将被选择，这是正确的路径（而不是声明中的S->B->E）

谢谢

最佳答案

dijkstra在扩展目标节点时终止。此外，我们在dijkstra中使用优先级队列（而不是队列），这样我们就可以扩展成本最低的节点所以在你的例子中A永远不会被扩展。

  open list = [ S cost:0 ] // priortiy queue
pop S out of open list
  closed list = [ S cost:0 ]
  open list = [ B cost:1 ; A cost:5 ]
pop B out of open list
  closed list = [ S cost:0 ; B cost:1 ]
  open list = [ E cost:2 ; A cost:5 ]
pop E out of open list
// it's better to terminate when we reach the goal but if we don't
// it doesn't make any difference we are going to find the shortest path
// to other nodes
   closed list = [ S cost:0 ; B cost:1 ; E cost:2 ]
   open list = [ A cost:5 ]
pop A out of open list
   // there isn't any nodes that we can push to open list
   closed list = [ S cost:0 ; B cost:1 ; E cost:2 ; A cost:5 ]
   open_list = []

dijkstra在展开节点时将其推送到其闭合列表中，因为它假设找到了指向它的最短路径。因此，即使我们没有在达到目标时终止，我们也永远不会扩展a，因为它在我们的封闭列表中。

关于algorithm - Dijkstra算法的一个负边缘失败示例，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39372808/