【正文】 5 8 V4 7 7 V5 7 10 V6 16 16 V7 14 14 V8 18 18 邊 0,10,20,31,42,43,54,64,75,76,87,8活動(dòng) a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14l e 0 2 3 0 2 3 0 0 3 0 0關(guān)鍵 是 是 是 是 是 是87利用關(guān)鍵路徑法求利用關(guān)鍵路徑法求 AOE網(wǎng)的各關(guān)鍵活動(dòng)網(wǎng)的各關(guān)鍵活動(dòng)void graph::CriticalPath ( ) {//在此算法中需要對(duì)鄰接表中單鏈表的結(jié)點(diǎn)加以//修改 , 在各結(jié)點(diǎn)中增加一個(gè) int域 cost, 記錄該結(jié)//點(diǎn)所表示的邊上的權(quán)值 。 int i, j。 int p, k。 int e, l。 Ve = new int[n]。 Vl = new int[n]。 for ( i = 0。 i n。 i++ ) Ve[i] = 0。//初始化 for ( i = 0。 i n。 i++ ) {//順向計(jì)算事件最早允許開始時(shí)間 Edgeint *p = NodeTable[i].adj。//該頂點(diǎn)邊鏈表鏈頭指針 p while ( p != NULL ) {//找所有后繼鄰接頂點(diǎn) k = p→ dest。//i的后繼鄰接頂點(diǎn) k if ( Ve[i] + p→ cost Ve[k] ) Ve[k] = Ve[i] + p→cost。 p = p→link。 //找下一個(gè)后繼 } 　88 } for ( i = 0。 i n。 i++ ) Vl[i] = Ve[n1]。//逆向計(jì)算事件的最遲開始時(shí)間 for ( i = n2。 i。 i ) {//按逆拓?fù)溆行蝽樞蛱幚? p = NodeTable[i].adj。 //該頂點(diǎn)邊鏈表鏈頭指針 p while ( p != NULL ) { k = p→ dest。 //i的后繼鄰接頂點(diǎn) k if ( Vl[k] p→ cost Vl[i]) Vl[i] = Vl[k] p→ cost。 p = p→ link。 //找下一個(gè)后繼 } } 89 for ( i = 0。 i n。 i++ ) {//逐個(gè)頂點(diǎn)求各活動(dòng)的 e[k]和 l[k] p = NodeTable[i].adj。 //該頂點(diǎn)邊鏈表鏈頭指針 p while ( p != NULL ) { k = p→ dest。 //k是 i的后繼鄰接頂點(diǎn) e = Ve[i]。 l = Vl[k] p→cost。 if ( l == e )/ /關(guān)鍵活動(dòng)cout i , k “” “是關(guān)鍵活動(dòng) ” endl。 p = p→ link。 //找 下一個(gè)后繼 } }} 90注意在拓?fù)渑判蚯笤谕負(fù)渑判蚯?Ve[i]和逆拓?fù)溆行蚯蠛湍嫱負(fù)溆行蚯?Vl[i]時(shí)時(shí) , 所需為所需為 O(n+e), 求各個(gè)活動(dòng)的求各個(gè)活動(dòng)的 e[k]和和 l[k]時(shí)所需時(shí)間為時(shí)所需時(shí)間為O(e), 總總 共花費(fèi)時(shí)間仍然是共花費(fèi)時(shí)間仍然是 O(n+e)。216。所有頂點(diǎn)按拓?fù)溆行虻拇涡蚓幪?hào)216。僅計(jì)算 Ve[i] 和 Vl[i] 是不夠的，還須計(jì)算 e[k] 和 l[k]。216。不是任一關(guān)鍵活動(dòng)加速一定能使整個(gè)工程提前。216。想使整個(gè)工程提前，要考慮各個(gè)關(guān)鍵路徑上所有關(guān)鍵活動(dòng)。91最短路徑 (Shortest Path)n 最短路徑問題： 如果從圖中某一頂點(diǎn) (稱為源點(diǎn) )到達(dá)另一頂點(diǎn) (稱為終點(diǎn) )的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。n 問題解法u 邊上權(quán)值非負(fù)情形的單源最短路徑問題 — Dijkstra算法u 邊上權(quán)值為任意值的單源最短路徑問題 — Bellman 和 Ford算法u 所有頂點(diǎn)之間的最短路徑 — Floyd 算法 92邊上權(quán)值非負(fù)情形的單源最短路徑問題n 問題的提法： 給定一個(gè)帶權(quán) 有向圖 D與源點(diǎn) v，求從 v 到 D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于 0。n 為求得這些最短路徑 , Dijkstra提出按路徑長度的遞增次序 , 逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn) v到其它各頂點(diǎn)的最短路徑全部求出為止。n 舉例說明93Dijkstra逐步求解的過程逐步求解的過程1043210 1003050206010源點(diǎn)源點(diǎn) 終點(diǎn)終點(diǎn) 最短路徑最短路徑 路徑長度路徑長度v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2) ?,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 94n 引入輔助數(shù)組 dist。 它的每一個(gè)分量 dist[i]表示當(dāng)前找到的從 源點(diǎn) v0到 終點(diǎn) vi 的最短路徑的長度。初始狀態(tài)：n 若從源點(diǎn) v0到頂點(diǎn) vi 有邊 , 則 dist[i]為該邊上的權(quán)值；n 若從源 點(diǎn) v0到頂點(diǎn) vi 無邊 , 則 dist[i]為 ? 。n 假設(shè) S 是已求得的最短路徑的終點(diǎn)的集合，則可證明： 下一條最短路徑必然是 從 v0 出發(fā)，中間只經(jīng)過 S 中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn) vx (vx?VS )的路徑中的一條。n 每次求得一條最短路徑后 , 其終點(diǎn) vk 加入集合S， 然后 對(duì)所有 的 vi ?VS， 修改其 dist[i]值 。95Dijkstra算法① 初始化： S ← { v 0 }。 dist[j] ← Edge[0][j], j = 1, 2, …, n1。 // n為圖中頂點(diǎn)個(gè)數(shù)② 求出最短路徑的長度： dist[k] ← min { dist[i] }, i ? V S 。 S ← S U { k }。③ 修改： dist[i] ← min{ dist[i], dist[k] + Edge[k][i] }, 對(duì)于每一個(gè) i ? V S 。 ④ 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) ② 。 96void ShortestPath (MTGraph G, int v ){//MTGraph是一個(gè)有 n 個(gè)頂點(diǎn)的帶權(quán)有向圖 ,各邊上的權(quán)值由 Edge[i][j]給出。//dist[j], 0? jn, 是當(dāng)前求到的從頂點(diǎn) v 到頂點(diǎn) j 的最短路徑長度 , 用數(shù)組 path[j], 0? jn, 存放求到的最短路徑。 EdgeData dist[]。 //最短路徑長度數(shù)組 int path[]。 //最短路徑數(shù)組 int S[]。 //最短路徑頂點(diǎn)集計(jì)算從單個(gè)頂點(diǎn)到其它各頂點(diǎn)最短路徑97 for ( int i = 0。 i n。 i++) { dist[i] = [v][i]。 //dist數(shù)組初始化 S[i] = 0。 //集合 S初始化 if ( i != v amp。amp。 dist[i] MaxValue ) path[i] = v。 else path[i] = 1。 //path數(shù)組初始化 } S[v] = 1。 dist[v] = 0。 //頂點(diǎn) v加入頂點(diǎn)集合 for ( i = 0。 i n1。 i++ ) {//從頂點(diǎn) v確定 n1條路徑 float min = MaxValue。 int u = v。 98 for ( int j = 0。 j n。 j++ ) //選當(dāng)前不在集合 S中具有最if ( !S[j] amp。amp。 dist[j] min )短路徑的頂點(diǎn) u { u = j。 min = dist[j]。 } S[u] = 1。 //將頂點(diǎn) u加入集合 S， 表示它已在最短路徑上 for ( int w = 0。 w n。 w++ ) //修改 if (!S[w] amp。amp。 [u][w] MaxValue amp。amp。 dist[u] + [u][w] dist[w] ) { //頂點(diǎn) w未加入 S, 且繞過 u可以縮短路徑 dist[w] = dist[u] + [u][w]。 path[w] = u。 //修改到 w的最短路徑 } } //選定各頂點(diǎn)到頂點(diǎn) v 的最短路徑}99//打印各頂點(diǎn)的最短路徑 : 路徑是逆向輸出的for ( i = 0。 i 。 i++ ) { cout endl。 cout “Distance: ” dist[i] “ Path: ” i。 //輸出終點(diǎn)的最短路徑長度和終點(diǎn) int pre = path[i]。 //取終點(diǎn)的直接前驅(qū) while ( pre != v ) { //沿路徑上溯輸出 cout “, ” pre。 pre = path[pre]。 }}10