數據結構羅吳蔓電子科大ppt考研chapt739-資料下載頁

　　

【正文】 l(i)=vl(k)dut(j,k) 4. 找出 e(i)=l(i)的活動，即為關鍵活動，諸關鍵活動組成的從源點到匯點的路徑即為 關鍵路徑 j k ai=dut(j,k) 關鍵路徑 四、例子 計算結果為： 頂點 Ve Vl 活動 弧 持續 T e l le 關鍵活動 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 關鍵路徑 ? 關鍵路徑上的活動都是關鍵活動。 ? 縮短非關鍵活動都不能縮短整個工期 如 a6縮短為 1，則整個工期仍為 8。 又如 a6推遲 3天開始，或拖延 3天完成 （ a6=6）均不影響整個工期 ? 分析關鍵路徑的目的是找出影響整個工期的關鍵活動，縮短關鍵活動的持續時間，常可以縮短整個工期。 如 a7縮短為 1，則整個工期為 7。 此時，再縮短任一關鍵活動均不能縮短整個工期。 即在有多條關鍵路徑時，縮短那些在所有關鍵路上的關鍵活動，才能縮短整個工期 ① ② ③ ④ ⑤ ⑥ a4=3 a2=2 a1=3 a5=4 a6=3 a7=2 a8=1 a3=2 關鍵路徑 1 2 3 4 5 6 7 8 9 6 4 5 1 1 2 9 7 4 2 4 又例 : 最短路徑 在有向圖中，尋找從某個源點到其余各個頂點或者每一對頂點之間的最短帶權路徑的運算，稱為最短路徑問題 一、某個源點到其余各頂點的最短路徑算法 迪杰斯特拉（ Dijkstra） 算法： ? 算法思想：按路徑長度遞增的次序產生到各頂點的最短路徑 ? 使用 DS： ? 利用帶權鄰接矩陣 cost ? 表示當前找到的從源點 V0到每個終點 Vi的最短路徑長度的輔助向量dist[i] ? 存儲最短路徑的向量 path[i] ? 表示已找到從 V0出發的最短路徑的終點的集合 S 最短路徑 ? 算法步驟： 1. 用 cost 初始化 dist；置 S={V0}； 2. 選擇 Vj,使得： dist[j]=Min{dist[i]|Vi∈ VS} Vj 就是當前求得的從 V0出發的最短路徑的終點，并將 Vj并入 S； 3. 對 VS上的所有頂點 Vk，修改： dist[k]=Min{dist[j]+cost[j, k], dist[k]} 4. 重復 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) 最短路徑 二、每一對頂點之間的最短路徑 兩種方法：每次以一個頂點為源點，重復調用 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