Weighted 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

私は意図的にvisited[]arrayを省略していました

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

しかし、トポロジカルソーティングを使用することにより、エッジが正確に1回訪問されるように、頂点を横断する順序が得られます。だから私たちはT.C.を保証することができましたの O(V+E).

だからで動作するように、この問題を解決するために O(V+E) トポロジカルソートを使用します。

しかし、私はこれでは十分ではないと思います、なぜここでトポロジカル順序付けを使用するのか、そしてそれが他の問題に役立つように知ってい

なぜトポロジカル順序付けなのか？

位相順序は私たちに次のような順序を与えます 0 1 2 3 4 5 次に、この順序でノードに到達すると（たとえば 4）それから我々はすでにそれへの最短パスを計算しました（4）タイプのすべてのエッジ（およびパス）として u -> v (v = 4）とすでに訪問されています。