算法合集之淺談最短徑路問題中的分層思想(參考版)
2024-10-21 18:37本頁面
【正文】 特別地，當同層的節(jié)點拓撲無關時 ， 就可以使用動態(tài)規(guī)劃代替最短路算法。 小結(jié) 分層圖的層是我們構(gòu)建模型時復制的，許多圖的元素都是相同或相似的，不需要增加額外的空間或操作。 那么總共有 O(nL)個階段，每個階段的轉(zhuǎn)移的復雜度 O(m)。 分析 — 算法三 — 轉(zhuǎn)移方程 令 f[i,j]表示到達城市 j長度為 i的所有路徑所花費的最少費用。 但是我們忽略了一個條件：道路長度是正整數(shù)，而不僅是非負整數(shù)。 時間復雜度降為 O(k(n2+m))。 按照費用從低到高的順序?qū)γ繉忧笞疃搪?，而非一次性對所有點求最短路。 時間復雜度為 O(k(kn2+m)) 。 1 5 4 2 3 6 1 5 4 2 3 6 1 5 4 2 3 6 …… 0 1 k 4 2 2 3 2 2 3 4 2 2 3 2 2 3 …… 分析 — 算法一 — 復雜度 由于道路長度是正整數(shù)，采用 Dijkstra算法求最短路。 1 5 4 2 3 6 2， 3 2， 4 3， 2
教學課件相關推薦
鄂ICP備17016276號-1