Weighted DAGで最短または最長のパスを見つけるためにトポロジカルソーティングを行うのはなぜですか?
-
29-09-2020 - |
質問
エッジの緩和を実行する前に、なぜトポロジカルソートを行う必要があるのか疑問に思っていました。
私たちが行う場合、それは良いだろうではないだろう :開始頂点が"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を省略していました
解決
このアルゴリズムを使用することにより、予想される時間の複雑さは次のようになりません 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
)とすでに訪問されています。
所属していません cs.stackexchange