algorithm - Dijkstra 的终止条件

Question

对于 Dijkstra，您可以使用结束条件

   while(!q.isEmpty()){
       //Some code
   }

但是如果知道结束节点，是不是就不能把结束条件改成

   while(!q.peek().equals(endNode){
       //Some code
   }

我见过的每个 Dijkstra 实现都使用较早的方法，但当您知道结束节点时，较晚的方法更快。还是这不再是 Dijkstra？

Answer 1

取决于您希望算法执行的操作。原始的 Dijkstra 算法计算从源到每个其他顶点的最短路径的长度。如果您只有一个目标顶点，则可以在将目标从队列中弹出后缩短算法。

捷径的正确性很容易证明:Dijkstra 永远不会更改已经从队列中弹出的节点的最短路径长度，因此您知道如果您继续运行算法直到队列为空。