【正文】 pre = path[pre]。 i++ ) { cout endl。 dist[u] + [u][w] dist[w] ) { //頂點 w未加入 S, 且繞過 u可以縮短路徑 dist[w] = dist[u] + [u][w]。 w++ ) //修改 if (!S[w] amp。 min = dist[j]。 j n。 i n1。 else path[i] = 1。 //dist數(shù)組初始化 S[i] = 0。 //最短路徑數(shù)組 int S[]。 96void ShortestPath (MTGraph G, int v ){//MTGraph是一個有 n 個頂點的帶權(quán)有向圖 ,各邊上的權(quán)值由 Edge[i][j]給出。 // n為圖中頂點個數(shù)② 求出最短路徑的長度： dist[k] ← min { dist[i] }, i ? V S 。n 假設 S 是已求得的最短路徑的終點的集合，則可證明： 下一條最短路徑必然是 從 v0 出發(fā)，中間只經(jīng)過 S 中的頂點便可到達的那些頂點 vx (vx?VS )的路徑中的一條。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點 v到其它各頂點的最短路徑全部求出為止。91最短路徑 (Shortest Path)n 最短路徑問題： 如果從圖中某一頂點 (稱為源點 )到達另一頂點 (稱為終點 )的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。216。 //找 下一個后繼 } }} 90注意在拓撲排序求在拓撲排序求 Ve[i]和逆拓撲有序求和逆拓撲有序求 Vl[i]時時 , 所需為所需為 O(n+e), 求各個活動的求各個活動的 e[k]和和 l[k]時所需時間為時所需時間為O(e), 總總 共花費時間仍然是共花費時間仍然是 O(n+e)。 //k是 i的后繼鄰接頂點 e = Ve[i]。 //找下一個后繼 } } 89 for ( i = 0。 i ) {//按逆拓撲有序順序處理 p = NodeTable[i].adj。 i n。//該頂點邊鏈表鏈頭指針 p while ( p != NULL ) {//找所有后繼鄰接頂點 k = p→ dest。 i++ ) Ve[i] = 0。 Ve = new int[n]。851324a1=8a2=12567 8a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58el0 0 8 12 12 22 22 28 40 460 0 8 12 12 32 22 28 40 461 2 3 4 5 6 7 8 9 1086事件 Ve[i] Vl[i] V0 0 0 V1 6 6 V2 4 6 V3 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 ( ) {//在此算法中需要對鄰接表中單鏈表的結(jié)點加以//修改 , 在各結(jié)點中增加一個 int域 cost, 記錄該結(jié)//點所表示的邊上的權(quán)值 。84n 這兩個遞推公式的計算必須分別在 拓撲有序及 逆拓撲有序 的前提下進行。n 為找出關鍵活動 , 需要求各個活動的 e[k] 與 l[k]， 以判別是否 l[k] == e[k]。 l[k] = Vl[j] dur(i, j)。② 事件 Vi 的最遲允許開始時間 Vl[i] 是在保證匯點 Vn1 在 Ve[n1] 時刻完成的前提下，事件 Vi 的允許的最遲開始時間。n 關鍵路徑上的所有活動都是關鍵活動 。 完成不同路徑的活動所需的時間雖然不同 , 但只有各條路徑上所有活動都完成了 , 整個工程才算完成。 } }} 78用邊表示活動的網(wǎng)絡 (AOE網(wǎng)絡 )n 如果在 無有向環(huán)的帶權(quán)有向圖 中 , 用有向邊表示一個工程中的活動 (Activity), 用邊上權(quán)值表示活動持續(xù)時間 (Duration), 用頂點表示事件 (Event), 則這樣的有向圖叫做用邊表示活動的網(wǎng)絡 , 簡稱 AOE ( Activity On Edges ) 網(wǎng)絡。 //輸出 EdgeNode * p = VexList[j].firstAdj。 i++ ) //期望輸出 n 個頂點 if ( StackEmpty(S) ) { //中途?？?,轉(zhuǎn)出 cout “網(wǎng)絡中有回路！ endl。 i n。76拓撲排序的算法void TopologicalSort (AdjGraph G) { Stack S。u 當入度為零的頂點棧不空時 , 重復執(zhí)行 ] 從頂點棧中退出一個頂點 , 并輸出之 。 VexList[j].firstAdj = p。n 在輸入數(shù)據(jù)前 , 頂點 表 VexList[ ]和入度數(shù)組count[ ]全部初始化 。 71C0 C1 C2C3 C4 C5拓撲排序的過程(a) 有向無環(huán)圖C2C5C1C0C3(b) 輸出頂點 C4C1 C2C5C3(c) 輸出頂點 C0C4C0 C2C5C1C3(d) 輸出頂點 C3 72C1 C2C5(e) 輸出頂點 C2C5C1(f) 輸出頂點 C1C5(g) 輸出頂點 C5 最后得到的拓撲有序序列為 C4 , C0 , C3 , C2 , C1 , C5 。 全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或216。令 n 為頂點個數(shù)。 n 這種構(gòu)造 AOV網(wǎng)絡全部頂點的拓撲有序序列的運算就叫做拓撲排序。如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件。用頂點表示活動的網(wǎng)絡 (AOV網(wǎng)絡 )65 C1 高等數(shù)學 C2 程序設計基礎 C3 離散數(shù)學 C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級語言程序設計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機原理 C8 課程代號 課程名稱 先修課程66學生課程學習工程圖C8C3C5C4C9C6C7C1C267n 可以用有向圖表示一個工程。完成了這些活動，這個工程就可以完成了。n 注意：當各邊有相同權(quán)值時，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。amp。 nearvex[v] = 1。 min = lowcost[j]。 j NumVertices。 i 。 //Vu到各點代價 nearvex[i] = u。 int * nearvex = new int[NumVertices]。53u 如果生成樹頂點集合外頂點 i 到剛加入該集合的新頂點 v 的距離比原來它到生成樹頂點集合中頂點的最短距離還要近，則修改 nearvex[i] : nearvex[i] = v。則選中的權(quán)值最小的邊為 (nearvex[v], v), 相應的權(quán)值為 lowcost[v]。 4925251050461322810251424221618 5046132 504613210原圖 (a) (b)504613210(c) (d) (e) (f)5046132102212504612102514221612325221250n 在構(gòu)造過程中，還設置了兩個輔助數(shù)組：u lowcost[ ] 存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點的各邊上的當前最小權(quán)值；u nearvex[ ] 記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近 (即權(quán)值最小 )。48普里姆 (Prim)算法n 普里