Dijkstra的最终条件

Question

使用Dijkstra,您可以使用最终条件

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

但是,如果您知道结束节点,是否无法将结束条件更改为

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

我见过的Dijkstra的每个实现都使用前面的版本,但是当你知道结束节点时,后者会更快.或者这不是Dijkstra了吗？

Answer 1

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

快捷方式的正确性可以很容易地证明:Dijkstra永远不会改变它已经从队列中弹出的节点的最短路径长度,所以你知道你正在查看如果你继续运行算法直到队列是空的.