1

在第 24 章第 658 页 CLRS 第三版中的 DIJKSTRA 伪代码中,在内部循环中,从新添加的顶点放松相邻边时,为什么允许边上的放松已经从队列中取出并添加到树的最短路径?

while(Q not empty){
 u = extractMin from Q;
 Add S to the shortest path tree;
 for each vertex v adjacent to u 
 relax(u,v,w)

}

为什么内部循环不检查顶点是否已经是最短路径树的一部分,例如,

while(Q not empty){
     u = extractMin from Q;
     Add S to the shortest path tree;
     for each vertex v adjacent to u 
     if v is in Q 
      then relax(u,v,w)

    }

哪个是正确的方法?

4

2 回答 2

2

首先要做的relax是检查

if v.d > u.d + w(u,v)

如果v已经在最短路径树上,则检查将始终失败并且relax不会继续。检查将if v is in Q是多余的。

然而,ifif v is in Q是一个比if v.d > u.d + w(u,v)算法的具体实现要快得多的操作,包括它可能是一个有用的优化。

于 2015-02-04T19:44:07.970 回答
2

这两种方法在功能上都是正确的。但是,您的版本不如 CLRS 版本最佳。你不想这样做,if v is in Q因为这是一个 O(log n) 操作,而if v.d > u.d + w(u, v)O(1) 是。在算法开始时,Q 包含图中的所有顶点。因此,比如说一个非常大的稀疏连接图,您的版本最终会比 CLRS 差得多。

但是,您的问题并非完全没有道理。在 CLRS 中对 Dijkstra 算法的解释有点令人困惑,这实际上是把我带到这个讨论线程的原因。查看第 658 页的伪代码:

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S = 0
3 Q = G.V
4 while Q not empty
5     u = EXTRACT-MIN(Q)
6     add u to S
7     for each vertex v in G.Adj[u]
8         RELAX(u, v, w)

有人想知道维护 S 的意义何在?如果我们通过删除第 2 行和第 6 行来完全取消它,该算法仍然有效,并且在它完成后,您可以通过在图形中向后跟随前导指针(已经存储在每个顶点中)打印最短路径(使用PRINT-PATH(G, s, v)第 601 页,如第 647 页所述)。S 似乎在这里更多地用作解释工具,以说明 Dijkstra 是一个贪心算法的事实,但在实际的图形实现中,在我看来它是不需要的。

于 2016-10-25T04:05:18.167 回答