Dijkstra算法与在拓扑排序图中松弛边的方法对于DAG的比较

Question

Dijkstra算法与在拓扑排序图中松弛边的方法对于DAG的比较

algorithmgraphgraph-theorydijkstra

4

我正在阅读《算法导论》第三版。书中提供了3种解决问题的方法，但我想询问其中两种方法。

无名算法：

该算法从DAG（详见22.4节）开始进行拓扑排序，以在顶点上施加线性排序。如果DAG包含从顶点u到顶点v的路径，则在拓扑排序中u位于v之前。我们在拓扑排序顺序上对顶点只进行一次遍历。在处理每个顶点时，我们松弛离开该顶点的每条边。

Dijkstra算法：

这个相当有名。

就本书所示而言，无名算法的时间复杂度为O(V+E)，而Dijkstra算法的时间复杂度为O(ElogV)。我们不能在负权重上使用Dijkstra算法，但我们可以使用另一种方法。除了可以用于循环算法外，使用Dijkstra算法的优点是什么？

- user4952610

1

@NursultanZarlyk。来自书籍：该算法的运行时间易于分析。如第22.4节所示，线路1的拓扑排序需要O（V + E）时间。第2行中INITIALIZESINGLE-SOURCE的调用需要O（V）时间。第3-5行的for循环每个顶点进行一次迭代。总体而言，第4-5行的for循环仅松弛每条边一次。（我们在这里使用了聚合分析。）由于内部for循环的每次迭代都需要O（1）时间，因此总运行时间为O（V + E），这是图的邻接列表表示大小的线性。 - user4952610

2

都对。如果图是一个有向无环图，其中每个前驱节点都与其所有后继节点相连，则第一个顶点将松弛V-1条边，第二个顶点将松弛V-2条边，以此类推直到最后一个顶点。在这种类型的图中，E ~ V^2，因此O(V^2 + E) = O(V + E) = O(V^2)。 - T. Claverie

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- T. Claverie · Accepted Answer

由于您提供的第一个算法仅适用于无环图，而Dijkstra算法适用于非负权重的图。这些限制不同。

在现实世界中，许多应用可以建模为具有非负权重的图，这就是为什么Dijkstra算法如此常用的原因。此外，它非常容易实现。Dijkstra算法的复杂度较高，因为它依赖于优先队列，但这并不意味着它一定需要更长的执行时间。（nlog(n)时间并不糟糕，因为log(n)是一个相对较小的数字：log(10^80) = 266）

然而，这只适用于稀疏图（边缘密度低）。对于密集图，其他算法可能更有效。