20拓?fù)渑判蚝完P(guān)鍵路徑(存儲(chǔ)版)
【正文】 e(i)=ve(j) l(i)=vl(k)dut(j,k) j k ai 如何求關(guān)鍵路徑 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 v1 v2 v3 v4 v5 v6 v7 v8 v9 ve vl 0 0 0 0 0 0 0 0 0 6 4 5 14 18 7 7 15 18 18 18 18 18 18 18 18 18 16 14 7 6 6 10 8 0 拓?fù)溆行蛐蛄?: v1 v2 v3 v4 v6 v5 v8 v7 v9 逆拓?fù)溆行蛐蛄?:v9 v7 v8 v5 v2 v3 v6 v4 v1 如何求關(guān)鍵路徑 a1 a2 a3 e l a4 a5 a6 a7 a8 a9 a10 a11 6 4 5 1 1 2 8 7 4 2 4 0 0 0 6 4 5 7 7 7 15 14 0 2 3 6 6 8 8 7 10 16 14 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 0, 0 6, 6 4, 6 5, 8 7, 7 7, 10 15, 16 14, 14 18, 18 如何求關(guān)鍵路徑 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 最終求得的關(guān) 鍵路徑如下所示： 關(guān)鍵路徑算法 1）輸入 n個(gè)頂點(diǎn)和 e條弧 j,k，建立 AOE網(wǎng)存儲(chǔ)結(jié)構(gòu) 2）求出網(wǎng) G的拓?fù)渑判? 令 ve[0]=0, 求其余結(jié)點(diǎn)的最早發(fā)生時(shí)間 ve(j)=max(ve(i) + dut(i,j)) i,j∈ T,T是以 j為頭的弧的集合 若得到拓?fù)渑判蛑许旤c(diǎn)個(gè)數(shù) n，說明 G中存在環(huán)，算法終止。i++){if(!indegree[i]) push(S,i)。 Push(T,j)。 } 關(guān)鍵路徑算法 Status CriticalPath( ALGragh G){//輸出 G的關(guān)鍵活動(dòng) if(!) ToplogicalOrder(G,T) return ERROR。 }//end of for }//end of while ………… }//end of CriticalPath 關(guān)鍵路徑算法 Status CriticalPath( ALGragh G){//輸出 G的關(guān)鍵活動(dòng) ………… for(j=0。 tag=(ee=el)?’*’:’’。 ee=ve[j]。 小結(jié)和作業(yè) 本節(jié)主要內(nèi)容： 3. 拓?fù)渑判蛩惴? 小結(jié)和作業(yè) 思考題： 下列關(guān)于 AOE網(wǎng)的敘述中，不正確的是（ ）。 p=pnextarc){ k=padjvex。 ee=ve[j]。 dut=*(pinfo)。 //入度 1為 0，則入棧 if((ve[j]+*(pinfo))ve[k]) ve[k]= ve[j]+*(pinfo) }//for }//while if (count) return ERROR。 } 關(guān)鍵路徑算法 Status ToplogicalOrder( ALGragh G, Stack amp。 for(i=0。 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 假設(shè)以 AOE網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1