我在教科书中看到了这段经文：
“如果图形是非循环的，我们可以改进Dijkstra算法 . 顶点可以按拓扑顺序选择，因为当选择顶点时，它的距离不能再降低，因为没有来自未知节点的入射边缘 . ”
我理解拓扑排序和Dijkstra的算法，但不理解拓扑顺序如何帮助加速Dijkstra，特别是当订单并不总是唯一时 . （除非它指的是没有意义的空间复杂性）
有人能解释一下如何改进它并举个例子吗？
您可以选择任意拓扑排序并按此顺序处理顶点 .
时间复杂度在图的大小上是线性的，因为不再需要优先级队列 . 您可以按拓扑顺序迭代所有顶点并计算它们的距离 .
它是这样的：
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 （通过拓扑顺序的定义） .
v
1 回答
您可以选择任意拓扑排序并按此顺序处理顶点 .
时间复杂度在图的大小上是线性的，因为不再需要优先级队列 . 您可以按拓扑顺序迭代所有顶点并计算它们的距离 .
它是这样的：
正确性来自这样一个事实，即当我们到达
v时，我们已经处理了所有具有边缘的顶点到v（通过拓扑顺序的定义） .