數(shù)據(jù)結構第19講關鍵路徑與最短路徑(編輯修改稿)
2025-06-18 00:10 本頁面
【文章內(nèi)容簡介】 對 i號頂點的每個鄰接點的入度減 l if(indegree[k]==0)Push(S， k)； //若入度減為 0，入棧 if(ve[j]+*(pinfo)ve[k] ) ve[k]=ve[j]+*(pinfo)； } //for *(pinfo)=dut(j,k) } //while if(count) return ERROR； //該有向網(wǎng)有回路 else return OK； } //TopologicalOrder 求關鍵路徑的算法 Status CriticalPath (ALGraph G){ //G為有向網(wǎng)，輸出 G的各項關鍵活動 if(!TopologicalOrder(G， T)) return ERROR； vl[0..]=ve[]； //初始化頂點事件的最遲發(fā)生時間 while(!StackEmpty(T)) //按拓撲逆序求各頂點的 vl值 for(Pop(T,j)， p=[j].firstarc； p； p=pnextarc){ k=padjvex； dut=*(p—info)； //dutj， k if(vl[k]dutvl[j]) vl[j]=vl[k]dut； } //for for(j=0； j； ++j) //求 ee， el和關鍵活動 for(p=[j]； p； p=pnextarc){ k=padjvex； dut=*(p—info)； ee=ve[j]； el=vl[k]dut； tag = (ee==e1) ? ‘*’:’’； printf(j， k， dut， ee， el， tag)； //輸出關鍵活動 } } //CriticalPath 例： 求下圖 AOE網(wǎng)的關鍵路徑 v1 v4 v6 v2 v3 v5 a6=3 e(s)＝ ve(i) l(s)＝ vl(j) dut(i， j) ve(源點 ) = 0 ； ve(j) = Max{ ve(i) + dut(i, j)} vl(匯點 ) = ve(匯點 )。 vl(i) = Min { vl(j) – dut(i, j)} 拓撲序列： V V V V V V6 頂點 ve vl 活動 e l le v1 0 0 a1 0 1 1 v2 3 4 a2 0 0 0 v3 2 2 a3 3 4 1 v4 6 6 a4 3 4 1 v5 6 7 a5 2 2 0 v6 8 8 a6 2 5 3 a7 6 6 0 a8 6 7 1 v1 v4 v6 v2 v3 v5 a6=3 練習：求下圖 AOE網(wǎng)的關鍵路徑 事件 j ev[ j ] Lv[ j ] 活動 i e [ i ] L [ i ] L [ i ] e [ i ] 1 0 0 1 0 0 0 2 6 6 2 0 2 2 3 4 6 3 0 3 3 4 5 8 4 6 6 0 5 7 7 5 4 6 2 6 7 10 6 5 8 3 7 16 16 7 7 7 0 11 14 14 0 10 16 16 0 9 18 18 9 7 10
教學課件相關推薦
鄂ICP備17016276號-1