Dijkstra 的拓扑排序算法

Question

我在教科书上看到这段话：

"If the graph is acyclic, we can improve Dijkstra’s algorithm. Vertices may be selected in topological order since when a vertex is selected, its distance can no longer be lowered, because there are no incoming edges from unknown nodes."

我了解拓扑排序和 Dijkstra 的算法，但不了解拓扑顺序如何帮助加快 Dijkstra 的速度，尤其是当顺序并不总是唯一的时候。（除非它指的是 space 复杂性，这也没有意义）

有人能解释一下它是如何改进的并举个例子吗？

Answer 1

您可以选择任意的拓扑排序并按此顺序处理顶点。

时间复杂度与图的大小呈线性关系，因为不再需要优先级队列。您可以按拓扑顺序遍历所有顶点并计算它们的距离。

它是这样的：

dist = 0 for the start vertex and +inf for the rest
for v in topological order:
     for u in neighbors[v] in reverse graph:
        dist[v] = min(dist[v], dist[u] + weight(u, v))

正确性源于这样一个事实，即当我们到达 v 时，我们已经处理了所有具有 v 边的顶点（根据拓扑顺序的定义）。

Dijkstra 的拓扑排序算法

Dijkstra's Algorithm with Topological Sort

algorithm

dijkstra

shortest-path

topological-sort