为什么我们要进行拓扑排序来找到加权 DAG 中的最短或最长路径？

Question

我想知道为什么我们需要在执行边缘松弛之前进行拓扑排序。

如果我们这样做不是更好吗：如果起始顶点是“s”

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

我故意遗漏了访问[]数组

Answer 1

通过使用该算法，预期的时间复杂度不会是 O(V+E) 因为我们必须多次访问边缘。

queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue

但是通过使用拓扑排序，我们可以获得遍历顶点的顺序，以便一条边仅被访问一次。所以我们可以保证 T.C.的 O(V+E).

所以要解决这个问题就必须在 O(V+E) 我们使用拓扑排序。

但我认为这还不够，我们还应该知道为什么在这里使用拓扑排序，以便它有助​​于解决其他问题。

为什么要拓扑排序？

拓扑排序给我们的顺序如下 0 1 2 3 4 5 然后，一旦我们到达这个顺序中的一个节点（比方说 4）那么我们已经计算出到达它的最短路径（4）作为类型的所有边（以及路径） u -> v (v = 4）并且已经被访问过。