[工學]數(shù)據(jù)機構(gòu)課件第7章圖-閱讀頁
2024-11-03 00:01本頁面
【正文】 a14=14 a15=10 最短路徑 路徑上的第一個頂點為 源點 (Source)，最后一個頂點為 終點 (Destination) 一、從某個源點到其余各頂點的最短路徑 v5 v0 v4 v1 v3 v2 100 60 30 10 10 5 50 20 迪杰斯特拉 (Dijkstra) 提出 按路徑長度遞增的次序 產(chǎn)生最短路徑的算法 D，每個分量 D[i] 表示當前所找到的從始點 v 到每個終點 vi的最短路徑 v=v0 v5 v0 v4 v1 v3 v2 100 60 30 10 10 5 50 20 1 2 3 4 5 D ∞ 10 ∞ 30 100 長度為 D[j] = Min{D[i] | vi∈ V} 的路徑就是從 v 出發(fā)的長度最短的一條最短路徑 (v， vj) 長度次短的路徑的終點是 vk，那么這條路徑只能是下列二者之一： ?(v， vk) ?(v， vj， vk) 假設(shè) S 為已求得最短路徑的終點的集合，則可證明：下一條最短路徑 (設(shè)其終點為 x) 或者是弧 (v， x)，或者是中間只經(jīng)過 S 中的頂點而最后到達頂點 x 的路徑 假設(shè) S 為已求得最短路徑的終點的集合，則可證明：下一條最短路徑 (設(shè)其終點為 x) 或者是弧 (v， x)，或者是中間只經(jīng)過 S 中的頂點而最后到達頂點 x 的路徑 證明：假設(shè) v 到 x 的最短路徑為 (v， … ， y， … ， x) 且此路徑上有一個頂點 y 不在 S 中，則說明存在一條終點不在 S 而長度比 (v， … ， y， … ， x) 更短的路徑 (v， … ， y) 但是，這是不可能的。 Dijkstra 算法求最短路徑的步驟 （ 1）初始化：第一組（集合 s）只含頂點 v1,第二組（集合 t）含有圖中其余頂點。若 v1到某頂點無邊， dist向量中的對應(yīng)值為無窮大。 s = s ∪ {j} （ 3） 修改從頂點 v1到集合 t(t=Vs)中各頂點的最短路徑長度 , 如果 dist[j]+arcs[j][k]dist[k] 則修改 dist[k]為 dist[k]=dist[j]+arcs[j][k] （ 4） 重復 （ 2） 、 （ 3） n1次 。 v5 v0 v4 v1 v3 v2 100 60 30 10 10 5 50 20 v0 v1 v2 v3 v4 v5 0 1 2 3 4 5 1 2 3 4 5 D ∞ 10 ∞ 30 100 ∞ 10 60 30 100 ∞ 10 50 30 90 ∞ 10 50 30 60 ∞ 10 50 30 60 Dijkstra 求最短路徑的算法分析 對于 n個頂點的圖 ， 求一個頂點到其余頂點的最短路徑 ， 循環(huán) n1次 ， 加上修改最短路徑的循環(huán) ， 是二層循環(huán) ， 故時間復雜度為 O(n2)。) ?方法二： 弗洛伊德 (Floyd)算法 – 算法思想：逐個頂點試探法 – 求最短路徑步驟 187。逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值 187。 2. 按深度優(yōu)先搜索序列、廣度優(yōu)先搜索序列輸出圖中結(jié)點。 A B D C F E D B F A C E 0 1 2 3 4 5 ∧ ∧ 5 0 1 1 ∧ 5 4 5 ∧ ∧ 0 ∧
教學課件相關(guān)推薦
鄂ICP備17016276號-1