Dijkstra结束条件

Question

对于Dijkstra，您使用结束条件。

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

但是，如果您知道结束节点，是否不可能将结束条件更改为

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

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

Answer 1

取决于你想要算法做什么。最初的Dijkstra算法计算从源到彼此顶点的最短路径的长度。如果您有一个目标顶点，则可以在将目标从队列中弹出后缩短该算法。

快捷方式的正确性可以很容易地被证明:Dijkstra从不改变它已经从队列中弹出的节点的最短路径长度，所以您知道如果您继续运行算法直到队列为空，您将看到它返回的长度。