algorithm - Dijkstra 算法因一个下降沿而失败的示例

Question

我正在尝试考虑一个所有边都具有正权重的图形，除了一条边，这样 Dijkstra 算法无法产生正确的输出。

我很乐意提出一个想法。

编辑:
我将此图视为反例，但我不明白为什么。顶点 A 将是最后一个从队列中弹出的，然后我们将 Relax() 边缘 A->E。因此将选择路径 S->A->E，这是正确的路径(而不是声称的 S->B->E)

谢谢

Answer 1

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，因为它在我们的封闭列表中。