【正文】 On Edge Network)。 工程至少需要的時間？ 工程中哪些是關(guān)鍵環(huán)節(jié)？ AOE網(wǎng)中源點到匯點的最長路徑 —— 關(guān)鍵路徑 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 11 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 60 關(guān)鍵路徑 —— 相關(guān)概念 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 11 在 AOE網(wǎng)中分別對應(yīng)一個頂點， 稱開始點（即入度為 0的頂點）為 源點 ， 稱結(jié)束點（即出度為 0的頂點）為 匯點。 整個工程所需要的最少時間不是所有活動所需時間的累加 , 而應(yīng)是從源點到匯點之間的 最長 的一條路徑。 稱這條最長的路徑為 關(guān)鍵路徑 (critical path)。 ?求解事件的 最早發(fā)生時間 ： 每個頂點事件的最早發(fā)生時間都依賴于其前驅(qū)頂點事件的最早發(fā)生時間。源點對應(yīng)事件的最早發(fā)生時間為 0 ?求解事件的 最遲發(fā)生時間 每個頂點事件的最遲發(fā)生時間都不能影響到后續(xù)各頂點的最遲發(fā)生時間。 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 61 關(guān)鍵路徑 ? 為求最長路經(jīng)，則需求各頂點對應(yīng)事件的最早發(fā)生時間 E[ ]。 ? 為不耽誤工期，則需求各頂點對應(yīng)時間的最遲發(fā)生時間 L[ ]. 如何判斷 AOE網(wǎng)中的關(guān)鍵路徑？ 關(guān)鍵路徑上的事件最早發(fā)生時間和最晚發(fā)生時間相等； 關(guān)鍵路徑上的活動的開始和結(jié)束事件發(fā)生的時間差等于活動的持續(xù)時間。 最早發(fā)生時間 ==最晚發(fā)生時間相等 關(guān)鍵路徑 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 62 關(guān)鍵路徑 —— 實例 關(guān)鍵路徑的求解方法及路徑 1 2 3 4 5 6 7 8 9 10 a1=3 a3=5 a2=4 a5=3 a4=6 a8=5 a9=4 a6=4 a10=3 a12=6 a11=4 a15=4 a14=6 a13=5 a7=3 3 4 5 9 8 14 13 12 19 19 15 13 14 9 10 7 6 3 0 0 關(guān)鍵路徑： （ 1,2,5,7,10）和（ 1,2,5,8,10） 關(guān)鍵活動： a1， a4， a8， a9， a13， a14 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 63 最短路徑 (Shortest path) ?從單個點到其余各點之間的最短路徑 ? Dijkstra算法 ?各點之間的最短路徑 ? Floyd算法 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 64 最短路徑 —— Dijkstra算法 ? 從單個點到其余各點間的最短路徑 —— Dijkstra算法 基本思想 按照最短路徑長度不減的次序求各頂點的解。 若已知道路 v0v1v2v3…v n1vn是 v0到 vn最近的路， 則途徑的某頂點 vi也為 v0到 vi最短的路。 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 2 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 65 最短路徑 —— Dijkstra算法實例 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 2 例 求下圖中頂點 1到其余各頂點的最短路徑。 0 12 3 ∞ ∞ ∞ 8 \ 5 \ 10 \ 14 \ 12 \ (1)初始化 :1到 v,若有邊 ,則 path[v]=邊 。dist[i]=邊的值 (2)選出 dist[i]為最小值 ,則 path[i]為 1到 i的最短路徑 (3)修改經(jīng)過 i更近的路徑 (4)重復(fù)（ 2）（ 3） 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 66 最短路徑 —— Dijkstra算法描述 方法如下： （其中： path[v]和 dist[v]表示從 v0到 v的最短路徑及其長度） （ 1）對 v0以外的各頂點 vi，若 v0,vi存在， 則將其作為 v0到 vi的（暫時的）最短路徑存放到 path[v]中， 將其權(quán)值作為對應(yīng)的路徑長度存放到 dist[v]中。 （ 2）從未解頂點中選擇一個 dist值最小的頂點 v， 則當(dāng)前的 path[v]和 dist[v]就是頂點 v的最終解。 （ 3）由于某些頂點經(jīng)過 v可能會使得從 v0到該頂點的路徑更近 一些，因此，應(yīng)修改這些頂點的路徑及其長度的值。 （ 4）重復(fù)（ 2）（ 3），直到所有頂點求解完畢。 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 67 最短路徑 —— Dijkstra算法實例 實例： 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 2 頂點 path dist 1 2 3 4 5 6 0 12 3 ∞ ∞ ∞ () (1,2) (1,3) () () () (1,3,2) 8 5 (1,3,4) (1,3,5) 10 (1,3,4,6) 14 (1,3,5,6) 12 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 68 最短路徑 —— Dijkstra算法實現(xiàn) 練習(xí)： void Dijkstra( graph G,amp。 path,int v0){ float dist[n]。 for(i=1。i=n。i++) { if(A[v0][i] !=∞) { dist[i]=A[v0][i]。 path[i]=v0,i。 } else{ dist[i]=∞。 path[i]={}。 } } for(i=1。i=n。i++) solved[i]=FALSE。 solved[v0]=TRUE。 for(i=1。i=n。i++){ mind= ∞。 for(j=1。j=n。j++) if( !solved[j] amp。amp。 dist[j] mind ) {mind=dist[j]。 v=j。} solved[v]=TRUE。 w=firstadj(G,v)。 while(w!=0){ if(dist[v]+A[v][w]dist[w]){ dist[w]=dist[v]+A[v][w]。 path[w]=path[v]+{w}。} w=nextadj(G,v,w)。 } } } ? 圖采用鄰接矩陣或鄰接表來存儲，算法復(fù)雜度均為Ｏ (n2)。 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 69 最短路徑 —— Dijkstra算法練習(xí) 練習(xí)： 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 70 最短路徑 —— Floyd算法 ? 各點間的最短路徑 —— Floyd算法 基本思想 通過矩陣序列實現(xiàn) A0,A1,…A n，其中 Ak中的 i,j代表 i到 j的最短路徑長度，中間經(jīng)過的頂點號不大于 k 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 71 最短路徑 —— Floyd算法實例 1 2 4 3 6 3 4 20 2 4 5 3 6 20 6 ∞ 2 4 7 4 22 ∞ 5 0 0 0 0 A2= 1 2 3 4 1 2 3 4 2 3 ∞ 4 ∞ 4 20 ∞ 6 ∞ ∞ 5 0 0 0 0 A0= 1 2 3 4 1 2 3 4 2 3 ∞ 4 7 4 20 22 6 ∞ ∞ 5 0 0 0 0 A1= 1 2 3 4 1 2 3 4 2 6 4 4 25 27 3 7 20 22 6 5 0 0 0 0 A3= 1 2 3 4 1 2 3 4 2 3 4 7 20 22 6 4 6 25 27 5 0 0 0 0 A4= 1 2 3 4 1 2 3 4 求各頂點間的最短路徑 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 72 最短路徑 —— Floyd算法實現(xiàn) Floyd算法的核心算法： for(k=1。k=n。k++) for(i=1。i=n。i++) for(j=1。j=n。j++) if ( A (k1) [i][k] + A (k1) [k][j] A (k1) [i][j] ) { A (k) [i][j] = A (k1) [i][k] + A (k1) [k][j]。 path[i][j] = path[i][k]+path[k][j]。 } else A (k) [i][j] = A (k1) [i][j]。 考慮用同一個矩陣 A節(jié)省矩陣序列的存儲，則上述算法轉(zhuǎn)化為： for(k=1。k=n。k++) for(i=1。i=n。i++) for(j=1。j=n。j++) if ( A[i][k]+A[k][j] A[i][j] ) { A[i][j]=A[i][k]+A[k][j]。 path[i][j]=path[i][k]+path[k][j]。} i j k ? 分析 算法復(fù)雜度均為Ｏ (n3) 合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院 73 謝謝！