給定一個有向圖 G = (V, E)，具有正邊和負邊??權重，但沒有回圈。讓 s ∈ V 是給定的源頂點。如何找到一種演算法來找到所有頂點到 s 的距離，據推測它的運行速度比 Bellman Ford 的 O(VE) 時間復雜度要快。
uj5u.com熱心網友回復：
如果圖形沒有環，那么您可以按拓撲順序處理頂點。
對于每個頂點v，如果它在距離d處可以從s到達，那么對于每個權重為w的邊(v,u) ，將u標記為權重為d w的可達性。如果你已經可以以較低的重量到達，那就別管它了。
因為您按拓撲順序處理圖，所以您知道當您處理一個頂點v時，您已經處理了它的所有前任，因此您將知道它從s開始的最短路徑的長度。當然，第一個可達頂點是s。
在可從s到達的頂點的子圖上，很容易將其與Kahn 的拓撲排序演算法相結合。
- 首先進行 BFS 搜索以查找從s可到達的所有頂點，并同時計算該子集中每個頂點的傳入邊。
- s將是計數為“0”的唯一頂點。它也與s有一個已知的 0 距離。把它放在一個佇列中。
- 雖然佇列中有頂點：
- 從佇列中移除一個頂點v
- 調整到其鄰居的距離
- 減少其鄰居的傳入邊數。如果任何鄰居的計數變為 0，則將其放入佇列中。
完成后，所有可到達的頂點都將被處理，并且它們的所有距離都將是已知的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417249.html
標籤：