Dijkstra 算法与 DAG 拓扑排序图中的松弛边
Dijkstra's algorithm vs relaxing edges in topologically sorted graph for DAG
我正在阅读算法导论第 3 版。给出了 3 种解决问题的方法。我的询问是关于其中两个。
无名之辈
The algorithm starts by topologically sorting the dag (see Section 22.4) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order. As we process each vertex, we relax each edge that leaves the vertex.
Dijkstra 算法
这是众所周知的
据书上显示，without name one 的时间复杂度是 O(V+E)，而 Dijstra 的时间复杂度是 O(ElogV)。我们不能在负权重上使用 Dijkstra，但我们可以使用另一个。使用Dijkstra算法除了可以用在循环算法中还有什么优点？
因为你给出的第一个算法只适用于无环图，而Dijkstra运行在非负权重的图上。
限制不一样。
在现实世界中，许多应用程序都可以建模为具有非负权重的图，这就是为什么使用 Dijkstra 的原因。另外，它实施起来非常简单。 Dijkstra 的复杂度更高，因为它依赖于优先级队列，但这并不意味着它需要更多的时间来执行。 (nlog(n) 时间还不错，因为 log(n) 是一个相对较小的数：log(10^80) = 266)
但是，这代表稀疏图（边缘密度低）。对于密集图，其他算法可能更有效。
我正在阅读算法导论第 3 版。给出了 3 种解决问题的方法。我的询问是关于其中两个。
无名之辈
The algorithm starts by topologically sorting the dag (see Section 22.4) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order. As we process each vertex, we relax each edge that leaves the vertex.
Dijkstra 算法
这是众所周知的
据书上显示，without name one 的时间复杂度是 O(V+E)，而 Dijstra 的时间复杂度是 O(ElogV)。我们不能在负权重上使用 Dijkstra，但我们可以使用另一个。使用Dijkstra算法除了可以用在循环算法中还有什么优点？
因为你给出的第一个算法只适用于无环图，而Dijkstra运行在非负权重的图上。 限制不一样。
在现实世界中，许多应用程序都可以建模为具有非负权重的图，这就是为什么使用 Dijkstra 的原因。另外，它实施起来非常简单。 Dijkstra 的复杂度更高，因为它依赖于优先级队列，但这并不意味着它需要更多的时间来执行。 (nlog(n) 时间还不错，因为 log(n) 是一个相对较小的数：log(10^80) = 266)
但是，这代表稀疏图（边缘密度低）。对于密集图，其他算法可能更有效。