【正文】 之和 ?關(guān)鍵路徑 —— 路徑長度最長的路徑叫 ~ ?Ve(j)—— 表示事件 Vj的最早發(fā)生時間 ?Vl(j)—— 表示事件 Vj的最遲發(fā)生時間 ?e(i)—— 表示活動 ai的最早開始時間 ?l(i)—— 表示活動 ai的最遲開始時間 ?l(i)e(i)—— 表示完成活動 ai的時間余量 ?關(guān)鍵活動 —— 關(guān)鍵路徑上的活動叫 ~，即 l(i)=e(i)的活動 ?問題分析 ?如何找 e(i)=l(i)的關(guān)鍵活動？ 設(shè)活動 ai用弧 j,k表示，其持續(xù)時間記為： dut(j,k) 則有：（ 1） e(i)=Ve(j) （ 2） l(i)=Vl(k)dut(j,k) j k ai ?如何求 Ve(j)和 Vl(j)？ (1)從 Ve(1)=0開始向前遞推 為頭的弧的集合是所有以其中 jTnjTjijidutiVeMa xjVei????????? 2,)} ,()({)((2)從 Vl(n)=Ve(n)開始向后遞推 為尾的弧的集合是所有以其中 iSniSjijidutjVlM i niVlj11,)} ,()({)( ???????????求關(guān)鍵路徑步驟 ?求 Ve(i) ?求 Vl(j) ?求 e(i) ?求 l(i) ?計算 l(i)e(i) 9 8 7 6 4 5 3 2 1 a6=2 V1 V2 V3 V4 V5 V6 V7 V8 V9 頂點(diǎn) Ve Vl 0 6 4 5 7 7 16 14 18 0 6 6 8 7 10 16 14 18 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 活動 e l le ? ? ? ? ? ? 0 0 0 0 2 2 6 6 0 4 6 2 5 8 3 7 7 0 7 7 0 7 10 3 16 16 0 14 14 0 0 3 3 =(a1+a4) (a2+a5) =18(a6+a9+a11) ?算法實(shí)現(xiàn) ?以鄰接表作存儲結(jié)構(gòu) ?從源點(diǎn) V1出發(fā)，令 Ve[1]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的 Ve[i] ?從匯點(diǎn) Vn出發(fā)，令 Vl[n]=Ve[n],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的 Vl[i] ?根據(jù)各頂點(diǎn)的 Ve和 Vl值，計算每條弧的 e[i]和 l[i],找出e[i]=l[i]的關(guān)鍵活動 鄰接表結(jié)點(diǎn)： typedef struct node { int vex。 //頂點(diǎn)域 int length。 struct node *next。 //鏈域 }JD。 表頭結(jié)點(diǎn)： typedef struct tnode { int vexdata。 int in。 //入度域 struct node *link。 //鏈域 }TD。 TD g[M]。 //g[0]不用 ?算法描述 ?輸入頂點(diǎn)和弧信息，建立其鄰接表 ?計算每個頂點(diǎn)的入度 ?對其進(jìn)行拓?fù)渑判? ?排序過程中求頂點(diǎn)的 Ve[i] ?將得到的拓?fù)湫蛄羞M(jìn)棧 ?按逆拓?fù)湫蛄星箜旤c(diǎn)的 Vl[i] ?計算每條弧的 e[i]和 l[i],找出 e[i]=l[i]的關(guān)鍵活動 9 8 7 6 4 5 3 2 1 a6=2 167。 最短路徑 ?問題提出 用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中： 頂點(diǎn) —— 表示城市 邊 —— 表示城市間的交通聯(lián)系 權(quán) —— 表示此線路的長度或沿此線路運(yùn)輸所花的時間或費(fèi)用等 問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑 —— 最短路徑 ?求從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 5 1 6 4 3 2 0 8 5 6 2 30 13 7 17 32 9 13 長度 最短路徑 V0,V1 V0,V2 V0,V2,V3 V0,V2,V3,V4 V0,V2,V3,V4,V5 V0,V1,V6 8 13 19 21 20 ?迪杰斯特拉 (Dijkstra)算法思想 按路徑長度遞增次序產(chǎn)生最短路徑算法： 把 V分成兩組： （ 1） S： 已求出最短路徑的頂點(diǎn)的集合 （ 2） VS=T： 尚未確定最短路徑的頂點(diǎn)集合 將 T中頂點(diǎn)按最短路徑遞增的次序加入到 S中， 保證：（ 1）從源點(diǎn) V0到 S中各頂點(diǎn)的最短路徑長度都不大于 從 V0到 T中任何頂點(diǎn)的最短路徑長度 （ 2）每個頂點(diǎn)對應(yīng)一個距離值 S中頂點(diǎn)：從 V0到此頂點(diǎn)的最短路徑長度 T中頂點(diǎn)：從 V0到此頂點(diǎn)的只包括 S中頂點(diǎn)作中間 頂點(diǎn)的最短路徑長度 依據(jù)：可以證明 V0到 T中頂點(diǎn) Vk的最短路徑，或是從 V0到 Vk的 直接路徑的權(quán)值；或是從 V0經(jīng) S中頂點(diǎn)到 Vk的路徑權(quán)值之和 （反證法可證） ?求最短路徑步驟 ?初始時令 S={V0},T={其余頂點(diǎn) }， T中頂點(diǎn)對應(yīng)的距離值 ?若存在 V0,Vi，為 V0,Vi弧上的權(quán)值 ?若不存在 V0,Vi， 為 ? ?從 T中選取一個其距離值為最小的頂點(diǎn) W，加入 S ?對 T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn) W作中間頂點(diǎn)，從 V0到 Vi的距離值比不加 W的路徑要短，則修改此距離值 ?重復(fù)上述步驟，直到 S中包含所有頂點(diǎn)，即 S=V為止 13 V0,V1 8 V0,V2 ? 30 V0,V4 ? 32 V0,V6 V2:8 V0,V2 13 V0,V1 13 V0,V2,V3 30 V0,V4 ? 32 V0,V6 V1:13 V0,V1 13 V0,V2,V3 30 V0,V4 22 V0,V1,V5 20 V0,V1,V6 V3:13 V0,V2,V3 19 V0,V2,V3,V4 22 V0,V1,V5 20 V0,V1,V6 V4:19 V0,V2,V3,V4 終點(diǎn) 從 V0到各終點(diǎn)的最短路徑及其長度 V1 V2 V3 V4 V5 V6 Vj 21 V0,V2,V3,V4,V5 20 V0,V1,V6 V6:20 V0, V1,V6 5 1 6 4 3 2 0 8 5 6 2 30 13 7 17 32 9 ?算法實(shí)現(xiàn) ?圖用帶權(quán)鄰接矩陣存儲 ad[][] ?數(shù)組 dist[]存放當(dāng)前找到的從源點(diǎn) V0到每個終點(diǎn)的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值 ?數(shù)組 pre[]表示從 V0到各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號；若從 V0到某終點(diǎn)無路徑，則用 0作為其前一頂點(diǎn)的序號 ?算法描述 6 2 7 5 4 3 1 8 5 6 2 30 13 7 17 32 9 ?????????????????????????????????????????????????????????017020605079032308131[][]addist 1 2 3 4 5 6 7 0 13 8 ? 30 ? 32 pre 1 2 3 4 5 6 7 0 1 1 0 1 0 1 (1) k=1 1 13 3 1 22 20 2 2 19 4 1 2151 1 1 長度 最短路徑 13 V1,V2 8 V1,V3 13 V1,V3,V4 19 V1,V3,V4,V5 21 V1,V3,V4,V5,V6 20 V1,V2,V7 ?算法分析： T(n)=O(n178。) 首先 :V3加進(jìn)來 ,(V1,V3,V4)=13 ?求每一對頂點(diǎn)之間的最短路徑 ?方法一：每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行 Dijkstra算法 n次 —— T(n)=O(n179。) ?方法二：弗洛伊德 (Floyd)算法 ?算法思想：逐個頂點(diǎn)試探法 ?求最短路徑步驟 ?初始時設(shè)置一個 n階方陣，令其對角線元素為 0，若存在弧Vi,Vj， 則對應(yīng)元素為權(quán)值；否則為 ? ?逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值 ?所有頂點(diǎn)試探完畢，算法結(jié)束 例 A C B 2 6 4 3 11 0 4 11 6 0 2 3 ? 0 初始： 路徑： AB AC BA BC CA 0 4 6 6 0 2 3 7 0 加入 V2： 路徑： AB ABC BA BC CA CAB 0 4 11 6 0 2 3 7 0 加入 V1： 路徑： AB AC BA BC CA CAB 0 4 6 5 0 2 3 7 0 加入 V3： 路徑： AB ABC BCA BC CA CAB ?算法實(shí)現(xiàn) ?圖用鄰接矩陣存儲 ?length[][]存放最短路徑長度 ?path[i][j]是從 Vi到 Vj的最短路徑上 Vj前一頂點(diǎn)序號 ?算法描述 例 1 3 2 2 6 4 3 11 初始： 0 4 11 6 0 2 3 ? 0 length= 1 1 1 1 1 1 1 1 1 path= 加入 V1： 0 4 11 6 0 2 3 7 0 length= 1 1 1 1 1 1 1 1 1 path= 加入 V2： 0 4 6 6 0 2 3 7 0 length= 1 1 2 1 1 1 1 1 1 path= 加入 V3： 0 4 6 5 0 2 3 7 0 length= 1 1 2 3 1 1 1 1 1 path= ?算法分析： T(n)=O(n179。)