多階段圖的複雜性

我正在瀏覽「計算機算法基礎」一書中的多階段圖問題。多階段圖的複雜性

它說：

Algorithm Graph(G,k,n,p) 
{ 
cost[n]=0; 
for j=n-1 to 1 step -1 do 
{ 
Let r be a vertex such that<j,r> is an edge of G and c[j,r]+cost[r] is minimum 
cost[j]=c[j,r]+cost[r] 
} 
}

筆者說，複雜度爲O（| V | + | E |）。凡| V |是頂點的數量和| E |是邊的數量。

我知道for循環運行的頂點總數，內線必須選擇一個近邊。

我不明白背後

來源

2012-03-22 user567879

如果每個頂點都保留其入射邊緣的列表，那麼每個邊緣將被檢查一次。 – 2012-03-22 06:04:29

邏輯爲了進一步的理解，看看Dijsktra算法上abritrary有向圖，每條邊只考慮一次爲好。運行時間爲O（| E | + | V lg V |）。

由於多級圖形被分割爲集合，因此您可以通過集合找到最短路徑，因爲您知道集合X中到目標節點的頂點必須在集合X-1之前訪問。你也知道同一組中的頂點在彼此之間沒有邊。簡而言之，您知道處理它們的順序，並且不必每次都考慮所有可能的頂點，如在Dijsktra

來源

2012-03-22 07:00:45 dfb

多階段圖的複雜性

回答

相關問題