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 回答