【正文】 事件 Vj的 最早 發(fā)生時(shí)間 Vl(j)——表示 事件 Vj的 最遲 發(fā)生時(shí)間 e(i)——表示 活動(dòng) ai的 最早 開始時(shí)間 l(i)——表示 活動(dòng) ai的 最遲 開始時(shí)間 l(i)e(i)——表示完成 活動(dòng) ai的時(shí)間 余量 關(guān)鍵活動(dòng) ——關(guān)鍵路徑上的活動(dòng)，即 l(i)=e(i)的活動(dòng) 第七章 圖 拓?fù)渑判? 整個(gè)工程完成的時(shí)間為 ：從有向圖的 源點(diǎn) 到 匯點(diǎn)的最長(zhǎng)路徑。 1 2 3 4 5 6 7 8 9 6 4 5 2 1 1 8 7 2 4 4 例如 : “關(guān)鍵活動(dòng) ”指的是 ：該弧上的 權(quán)值增加 將使有向圖上的 最長(zhǎng)路徑的長(zhǎng)度增加。 源點(diǎn) 匯點(diǎn) 第七章 圖 拓?fù)渑判? 如何求關(guān)鍵活動(dòng)？ 該活動(dòng)的 最早 開始時(shí)間 = 該活動(dòng)的 最遲 開始時(shí)間 i j dut 問(wèn)題分析 持續(xù)時(shí)間 第七章 圖 拓?fù)渑判? ―事件 (頂點(diǎn) )‖ 的 最早發(fā)生時(shí)間 ve(j) ve(j) = 從源點(diǎn)到頂點(diǎn) j的最長(zhǎng)路徑長(zhǎng)度 。 ―事件 (頂點(diǎn) )‖ 的 最遲發(fā)生時(shí)間 vl(k) vl(k) = 從頂點(diǎn) k到匯點(diǎn)的最短路徑長(zhǎng)度 。 第七章 圖 拓?fù)渑判? 假設(shè)第 i 條弧為 j, k 則 對(duì)第 i 項(xiàng)活動(dòng)言 “活動(dòng) (弧 )‖的 最早開始時(shí)間 ee(i) ee(i) = ve(j)。 ―活動(dòng) (弧 )‖的 最遲開始時(shí)間 el(i) el(i) = vl(k) – dut(j,k)。 第七章 圖 拓?fù)渑判? 事件發(fā)生時(shí)間的計(jì)算公式 : ve(源點(diǎn) ) = 0。 ve(k) = Max{ve(j) + dut(j, k)} vl(匯點(diǎn) ) = ve(匯點(diǎn) )。 vl(j) = Min{vl(k) – dut(j, k)} 第七章 圖 拓?fù)渑判? 1 2 3 4 5 6 7 8 9 6 4 5 2 1 1 8 7 2 4 4 拓?fù)溆行蛐蛄?: 1 4 6 3 2 5 8 7 9 1 2 3 4 5 6 7 8 9 ve vl 0 0 0 0 0 0 0 0 0 6 4 5 7 11 57 15 14 18 18 18 18 18 18 18 18 18 18 16 148 6 6 108 0 7 第七章 圖 拓?fù)渑判? 1 2 3 4 5 6 7 8 9 ve vl 0 6 4 5 7 7 15 14 18 18 14 16 10 7 8 6 6 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a 1 1 權(quán) 6 4 5 1 1 2 8 7 4 2 4 e l l e =0 0 0 0 6 4 5 7 7 7 15 14 14 16 0 2 3 6 6 8 8 7 10 第七章 圖 拓?fù)渑判? 求關(guān)鍵路徑步驟 求 Ve(i) 求 Vl(j) 求 e(i) 求 l(i) 計(jì)算 l(i)e(i) 1 2 3 4 5 6 7 8 9 ve vl 0 6 4 5 7 7 15 14 18 18 14 16 10 7 8 6 6 0 1 2 3 4 5 6 7 8 9 6 4 5 2 1 1 8 7 2 4 4 第七章 圖 拓?fù)渑判? 算法實(shí)現(xiàn) 以鄰接表作存儲(chǔ)結(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值，計(jì)算每條弧的 e[i]和 l[i],找出 e[i]=l[i]的關(guān)鍵活動(dòng) 要點(diǎn)： 顯然，求 ve的順序應(yīng)該是 按拓?fù)溆行?的 次序 。 而 求 vl的順序應(yīng)該是 按拓?fù)淠嫘?的 次序 。 因?yàn)? 拓?fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄校? 因此 應(yīng)該在拓?fù)渑判虻倪^(guò)程中，另設(shè)一個(gè) “棧” 記下拓?fù)溆行蛐蛄小? 第七章 圖 拓?fù)渑判? 算法描述 輸入頂點(diǎn)和弧信息，建立其鄰接表 計(jì)算每個(gè)頂點(diǎn)的入度 對(duì)其進(jìn)行拓?fù)渑判? ?排序過(guò)程中求頂點(diǎn)的 Ve[i] ?將得到的拓?fù)湫蛄羞M(jìn)棧 按逆拓?fù)湫蛄星箜旤c(diǎn)的 Vl[i] 計(jì)算每條弧的 e[i]和 l[i],找出 e[i]=l[i]的關(guān)鍵活動(dòng) 改寫算法 第七章 圖 最短路徑 每一對(duì)頂點(diǎn) 之間的最短路徑 從某個(gè)源點(diǎn)到 其余各點(diǎn)的最短路徑 第七章 圖 最短路徑 ? 問(wèn)題提出 用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng) 圖中： 頂點(diǎn) ——表示城市 邊 ——表示城市間的交通聯(lián)系 權(quán) ——表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等 問(wèn)題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑 ——最短路徑 第七章 圖 最短路徑 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 24 15 8 6 3 9 7 3 5 10 4 a f e d b c g 2 最短路徑 長(zhǎng)度 a,d,g,b 22 a,c 8 a,d 15 a,c,f,e 13 a,c,f 11 a,g 19 第七章 圖 最短路徑 求 從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想 : 依 最短路徑的長(zhǎng)度 遞增的次序求得各條路徑 源點(diǎn) v1 … 其中， 從源點(diǎn)到頂點(diǎn) v1的最短路徑 是所有最短路徑中長(zhǎng)度最短者。 v2 第七章 圖 最短路徑 在這條路徑上， 必定只含一條弧 ，并且這條弧是所有從源點(diǎn)出發(fā)的弧中 權(quán)值最小。 下一條 路徑長(zhǎng)度次短 的最短路徑的特點(diǎn) : 路徑長(zhǎng)度最短 的最短路徑的特點(diǎn) : 它只可能有兩種情況 :或者是 直接從源點(diǎn)到該點(diǎn) (只含一條弧 )； 或者是， 從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v1，再到達(dá)該頂點(diǎn) (由兩條弧組成 )。 第七章 圖 最短路徑 其余最短路徑的特點(diǎn)： 再下一條 路徑長(zhǎng)度次短 的最短路徑的特點(diǎn) : 它可能有三種情況：或者是， 直接從源點(diǎn)到該點(diǎn) (只含一條弧 )； 或者是， 從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v1，再到達(dá)該頂點(diǎn) (由兩條弧組成 )；或者是，從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v2，再到達(dá)該頂點(diǎn)。 它或者是 直接從源點(diǎn)到該點(diǎn) (只含一條弧 )； 或者是， 從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn) 。 第七章 圖 最短路徑 求最短路徑的迪杰斯特拉算法： 一般情況下 : Dist[k] = 源點(diǎn)到頂點(diǎn) k 的弧上的權(quán)值 或者 = 源點(diǎn)到 其它頂點(diǎn) 的路徑長(zhǎng)度 +其它頂點(diǎn) 到頂點(diǎn) k 的 弧上的權(quán)值 設(shè)置輔助數(shù)組 Dist，其中每個(gè)分量Dist[k] 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。 第七章 圖 最短路徑 1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。 2）修改其它各頂點(diǎn)的 Dist[k]值。 假設(shè)求得最短路徑的頂點(diǎn)為 u， 若 Dist[u]+[u][k]Dist[k] 則將 Dist[k] 改為 Dist[u]+[u][k] ????INF INIT Ykvar c sGkD i s t]][0[.][V0和 k之間存在弧 V0和 k之間不存在弧 其中的最小值即為最短路徑的長(zhǎng)度 。 第七章 圖 最短路徑 0 24 8 15 ? ? ? ? 0 ? ? 6 ? ? ? ? 0 ? 7 3 ? ? ? ? 0 ? ? 4 ? ? ? ? 0 ? 9 ? ? ? 5 2 0 10 ? 3 ? ? ? ? 0 a b c d e f g 頂點(diǎn) a 為源點(diǎn)，設(shè)定 dist和 path的初始值，頂點(diǎn) a 并入集合 S 選出 dist 中的最小值在 i=2，求得第一條最短路徑 {ac},頂點(diǎn) c 并入集合 S 考察從頂點(diǎn) c 出發(fā)的弧，修正集合VS中頂點(diǎn)的 dist 和 path 的值 中的最小值在 5，求得第 2 條最短路徑 {acf},頂點(diǎn) f 并入集合 S考察從頂點(diǎn) f 出發(fā)的弧，修正集合 VS中頂點(diǎn)的 dist 和 path 的值 中的最小值在 4，求得第 3 條最短路徑 e},頂點(diǎn) e 并入集合 S 考察從頂點(diǎn) e 出發(fā)的弧，修正集合 中頂點(diǎn)的 和中的最小值在 3，求得第 4 條最短路徑 ad},頂點(diǎn) d 并入集合 考察從頂點(diǎn) d 出發(fā)的弧，修正集合 S中頂點(diǎn)的 和中的最小值在 6，求得第 5 條最短路徑 g},頂點(diǎn) g并入集合 考察從頂點(diǎn) g 出發(fā)的弧，修正集合中頂點(diǎn)的 和中的最小值在 1，求得第 6 條最短路徑 b 頂點(diǎn) b并入集合 i 0 1 2 3 4 5 6 S dist[i] path[i] 24 ab 8 ac 15 ad a c 15 ace 11 acf acff 13 acfe21 acfg ac e d 19dg ad g 22 adgb b adgb 24 15 8 6 3 9 7 3 5 10 4 a f e d b c g 2 第七章 圖 最短路徑 求每一對(duì)頂點(diǎn)之間的最短路徑 ?方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行 Dijkstra算法 n次 — —— T(n)=O(n179。) ?方法二：弗洛伊德 (Floyd)算法 算法思想：逐個(gè)頂點(diǎn)試探法 求最短路徑步驟 第七章 圖 最短路徑 依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長(zhǎng)度最小者。 若 vi,vj存在，則存在路徑 {vi,vj} // 路徑中不含其它頂點(diǎn) 若 vi,v1,v1,vj存在，則存在路徑 {vi,v1,vj} // 路徑中所含頂點(diǎn)序號(hào)不大于 1 若 {vi,… ,v2}, {v2,… ,vj}存在，則存在一條路徑 {vi, … , v2, … vj} // 路徑中所含頂點(diǎn)序號(hào)不大于 2 … 第七章 圖 本章小結(jié) 1. 熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。 2. 熟練掌握?qǐng)D的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。 第七章 圖 本章小結(jié) 3. 熟練掌握最小生成樹的構(gòu)造方法，選點(diǎn)法和選邊法。 4。熟練掌握拓?fù)渑判蚍椒? 4. 理解求解關(guān)鍵路徑和兩頂點(diǎn)間最短路徑問(wèn)題。 5. 理解教科書中討論的各種圖的算法。