logo标签列表

迪杰斯特拉算法的终止条件

algorithmgraphdijkstra
6

使用Dijkstra算法时需要考虑终止条件。

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

但是如果你知道结束节点，难道不能改变结束条件为：
   while(!q.peek().equals(endNode){
       //Some code
   }

我见过的所有 Dijkstra 的实现都使用了早期的算法，但是如果你知道终点节点，后一种算法更快。或者这已经不是 Dijkstra 算法了吗？
1个回答
15

取决于您想让算法做什么。原始的Dijkstra算法计算源点到每个其他顶点的最短路径长度。如果您只有一个目标顶点，可以在弹出目标节点后缩短算法。

缩短算法的正确性可以很容易地证明：Dijkstra从未更改已经弹出队列的节点的最短路径长度，因此您知道您看到的是它在将算法运行直到队列为空时返回的长度。

是的，我有一个单一的目标顶点。但这仍然是Dijkstra算法的正确实现吗？还是可以说这不再是Dijkstra算法了？ - SBylemans
1
@Rednas 这只是术语的问题。 Dijkstra算法存在多个变体，当您提前停止算法时，基本属性包括最坏情况下的复杂度不会改变。 - Fred Foo
好的，谢谢。我执行了后面的条件，执行时间大约减少了一半 :p - SBylemans
我认为它可以重新排队顶点，如果有另一条路径的话？而且如果你提前结束，这不意味着你可能会错过另一条更短的路径吗？ - Strawberry
1
@Strawberry 我有同样的问题，但我认为不是这样的，因为队列按照距离起始顶点最近到最远的顶点排序。假设Z是终点顶点，并且在队列的顶部，其值为30。Y在队列中位于其下方并链接到Z。但是这条路径总是>= 30，否则Y将在队列中高于Z。所以可以安全地提前结束。 - branweb
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接