數(shù)據(jù)結(jié)構(gòu)羅吳蔓電子科大ppt考研chapt739-資料下載頁
2025-01-01 16:07本頁面
【正文】 l(i)=vl(k)dut(j,k) 4. 找出 e(i)=l(i)的活動，即為關(guān)鍵活動，諸關(guān)鍵活動組成的從源點到匯點的路徑即為 關(guān)鍵路徑 j k ai=dut(j,k) 關(guān)鍵路徑 四、例子 計算結(jié)果為： 頂點 Ve Vl 活動 弧 持續(xù) T e l le 關(guān)鍵活動 V1 0 0 a1 1,2 3 0 1 1 V2 3 4 a2 1,3 2 0 0 0 a2 V3 2 2 a3 2 3 4 1 V4 6 6 a4 2,5 3 3 4 1 V5 6 7 a5 3,4 4 2 2 0 a5 V6 8 8 a6 3,6 3 2 5 3 a7 4,6 2 6 6 0 a7 Max + Min a8 5,6 1 6 7 1 ① ② ③ ④ ⑤ ⑥ a4=3 a2=2 a1=3 a5=4 a6=3 a7=2 a8=1 a3=2 關(guān)鍵路徑 ? 關(guān)鍵路徑上的活動都是關(guān)鍵活動。 ? 縮短非關(guān)鍵活動都不能縮短整個工期 如 a6縮短為 1，則整個工期仍為 8。 又如 a6推遲 3天開始，或拖延 3天完成 （ a6=6）均不影響整個工期 ? 分析關(guān)鍵路徑的目的是找出影響整個工期的關(guān)鍵活動，縮短關(guān)鍵活動的持續(xù)時間，?？梢钥s短整個工期。 如 a7縮短為 1，則整個工期為 7。 此時，再縮短任一關(guān)鍵活動均不能縮短整個工期。 即在有多條關(guān)鍵路徑時，縮短那些在所有關(guān)鍵路上的關(guān)鍵活動，才能縮短整個工期 ① ② ③ ④ ⑤ ⑥ a4=3 a2=2 a1=3 a5=4 a6=3 a7=2 a8=1 a3=2 關(guān)鍵路徑 1 2 3 4 5 6 7 8 9 6 4 5 1 1 2 9 7 4 2 4 又例 : 最短路徑 在有向圖中，尋找從某個源點到其余各個頂點或者每一對頂點之間的最短帶權(quán)路徑的運算，稱為最短路徑問題 一、某個源點到其余各頂點的最短路徑算法 迪杰斯特拉（ Dijkstra） 算法： ? 算法思想：按路徑長度遞增的次序產(chǎn)生到各頂點的最短路徑 ? 使用 DS： ? 利用帶權(quán)鄰接矩陣 cost ? 表示當(dāng)前找到的從源點 V0到每個終點 Vi的最短路徑長度的輔助向量dist[i] ? 存儲最短路徑的向量 path[i] ? 表示已找到從 V0出發(fā)的最短路徑的終點的集合 S 最短路徑 ? 算法步驟： 1. 用 cost 初始化 dist；置 S={V0}； 2. 選擇 Vj,使得： dist[j]=Min{dist[i]|Vi∈ VS} Vj 就是當(dāng)前求得的從 V0出發(fā)的最短路徑的終點，并將 Vj并入 S； 3. 對 VS上的所有頂點 Vk，修改： dist[k]=Min{dist[j]+cost[j, k], dist[k]} 4. 重復(fù) 2， 3， n1次。 最短路徑 ? 例子 ① ② ③④⑤0 5 10 50 30 100 60 10 20 cost 0 1 2 3 4 5 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞ ∞∞ 10 5 ∞∞∞∞∞∞∞ 50 20 30 ∞∞∞∞100 10 60 ∞0 1 2 3 4 5 終點 從 v0 到各終點的 dist 值和最短路徑 v1 v2 v4 v3 v5 vj 60(v0,v4,v3,v5) v5 ∞50(v0,v4,v3) 90(v0,v4,v5) v3 ∞ ∞10(v0,v2) 30(v0,v4) 100(v0,v5) v2 ∞∞ 60(v0,v2,v3) v4 ∞30(v0,v4) 100(v0,v5) 最短路徑 二、每一對頂點之間的最短路徑 兩種方法：每次以一個頂點為源點，重復(fù)調(diào)用 Dijkstra算法 n次； 弗洛伊德算法 (Floyd) ：以 A(0) [i,j]=cost[i,j] 遞推出：A(k)[i,j]=Min{A(k1)[i,j], A(k1)[i,k]+ A(k1) [k,j]},1≤k≤n 其中， A[k][i,j] 表示從 vi到 vj 的中間頂點的序號不大于 k 的最短路徑長度。最后得到的 A[n][i,j]就是從 vi 到 vj 的最短路徑長度。 最短路徑 ∞ 4 11 ∞∞∞6 2 3 ① ②③6 4 3 11 2 A B C 1 2 3 A(0) A(1) A(2) A(3) A 4 11 6 ∞∞6 2 5 3 7 ∞∞1 2 3 1 2 3 1 2 3 1 2 3 ∞ ∞ ∞ 3 7 4 6 2 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1