【正文】 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活動 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關鍵 是 是 是 是 是 是87利用關鍵路徑法求利用關鍵路徑法求 AOE網(wǎng)的各關鍵活動網(wǎng)的各關鍵活動void graph::CriticalPath ( ) {//在此算法中需要對鄰接表中單鏈表的結點加以//修改 , 在各結點中增加一個 int域 cost, 記錄該結//點所表示的邊上的權值 。 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++ ) {//順向計算事件最早允許開始時間 Edgeint *p = NodeTable[i].adj。//該頂點邊鏈表鏈頭指針 p while ( p != NULL ) {//找所有后繼鄰接頂點 k = p→ dest。//i的后繼鄰接頂點 k if ( Ve[i] + p→ cost Ve[k] ) Ve[k] = Ve[i] + p→cost。 p = p→link。 //找下一個后繼 } 　88 } for ( i = 0。 i n。 i++ ) Vl[i] = Ve[n1]。//逆向計算事件的最遲開始時間 for ( i = n2。 i。 i ) {//按逆拓撲有序順序處理 p = NodeTable[i].adj。 //該頂點邊鏈表鏈頭指針 p while ( p != NULL ) { k = p→ dest。 //i的后繼鄰接頂點 k if ( Vl[k] p→ cost Vl[i]) Vl[i] = Vl[k] p→ cost。 p = p→ link。 //找下一個后繼 } } 89 for ( i = 0。 i n。 i++ ) {//逐個頂點求各活動的 e[k]和 l[k] p = NodeTable[i].adj。 //該頂點邊鏈表鏈頭指針 p while ( p != NULL ) { k = p→ dest。 //k是 i的后繼鄰接頂點 e = Ve[i]。 l = Vl[k] p→cost。 if ( l == e )/ /關鍵活動cout i , k “” “是關鍵活動 ” endl。 p = p→ link。 //找 下一個后繼 } }} 90注意在拓撲排序求在拓撲排序求 Ve[i]和逆拓撲有序求和逆拓撲有序求 Vl[i]時時 , 所需為所需為 O(n+e), 求各個活動的求各個活動的 e[k]和和 l[k]時所需時間為時所需時間為O(e), 總總 共花費時間仍然是共花費時間仍然是 O(n+e)。216。所有頂點按拓撲有序的次序編號216。僅計算 Ve[i] 和 Vl[i] 是不夠的，還須計算 e[k] 和 l[k]。216。不是任一關鍵活動加速一定能使整個工程提前。216。想使整個工程提前，要考慮各個關鍵路徑上所有關鍵活動。91最短路徑 (Shortest Path)n 最短路徑問題： 如果從圖中某一頂點 (稱為源點 )到達另一頂點 (稱為終點 )的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。n 問題解法u 邊上權值非負情形的單源最短路徑問題 — Dijkstra算法u 邊上權值為任意值的單源最短路徑問題 — Bellman 和 Ford算法u 所有頂點之間的最短路徑 — Floyd 算法 92邊上權值非負情形的單源最短路徑問題n 問題的提法： 給定一個帶權 有向圖 D與源點 v，求從 v 到 D中其它頂點的最短路徑。限定各邊上的權值大于或等于 0。n 為求得這些最短路徑 , Dijkstra提出按路徑長度的遞增次序 , 逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點 v到其它各頂點的最短路徑全部求出為止。n 舉例說明93Dijkstra逐步求解的過程逐步求解的過程1043210 1003050206010源點源點 終點終點 最短路徑最短路徑 路徑長度路徑長度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。 它的每一個分量 dist[i]表示當前找到的從 源點 v0到 終點 vi 的最短路徑的長度。初始狀態(tài)：n 若從源點 v0到頂點 vi 有邊 , 則 dist[i]為該邊上的權值；n 若從源 點 v0到頂點 vi 無邊 , 則 dist[i]為 ? 。n 假設 S 是已求得的最短路徑的終點的集合，則可證明： 下一條最短路徑必然是 從 v0 出發(fā)，中間只經(jīng)過 S 中的頂點便可到達的那些頂點 vx (vx?VS )的路徑中的一條。n 每次求得一條最短路徑后 , 其終點 vk 加入集合S， 然后 對所有 的 vi ?VS， 修改其 dist[i]值 。95Dijkstra算法① 初始化： S ← { v 0 }。 dist[j] ← Edge[0][j], j = 1, 2, …, n1。 // n為圖中頂點個數(shù)② 求出最短路徑的長度： dist[k] ← min { dist[i] }, i ? V S 。 S ← S U { k }。③ 修改： dist[i] ← min{ dist[i], dist[k] + Edge[k][i] }, 對于每一個 i ? V S 。 ④ 判斷：若 S = V, 則算法結束，否則轉 ② 。 96void ShortestPath (MTGraph G, int v ){//MTGraph是一個有 n 個頂點的帶權有向圖 ,各邊上的權值由 Edge[i][j]給出。//dist[j], 0? jn, 是當前求到的從頂點 v 到頂點 j 的最短路徑長度 , 用數(shù)組 path[j], 0? jn, 存放求到的最短路徑。 EdgeData dist[]。 //最短路徑長度數(shù)組 int path[]。 //最短路徑數(shù)組 int S[]。 //最短路徑頂點集計算從單個頂點到其它各頂點最短路徑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。 //頂點 v加入頂點集合 for ( i = 0。 i n1。 i++ ) {//從頂點 v確定 n1條路徑 float min = MaxValue。 int u = v。 98 for ( int j = 0。 j n。 j++ ) //選當前不在集合 S中具有最if ( !S[j] amp。amp。 dist[j] min )短路徑的頂點 u { u = j。 min = dist[j]。 } S[u] = 1。 //將頂點 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] ) { //頂點 w未加入 S, 且繞過 u可以縮短路徑 dist[w] = dist[u] + [u][w]。 path[w] = u。 //修改到 w的最短路徑 } } //選定各頂點到頂點 v 的最短路徑}99//打印各頂點的最短路徑 : 路徑是逆向輸出的for ( i = 0。 i 。 i++ ) { cout endl。 cout “Distance: ” dist[i] “ Path: ” i。 //輸出終點的最短路徑長度和終點 int pre = path[i]。 //取終點的直接前驅 while ( pre != v ) { //沿路徑上溯輸出 cout “, ” pre。 pre = path[pre]。 }}10