20拓?fù)渑判蚝完P(guān)鍵路徑-文庫(kù)吧資料
2024-08-07 15:49本頁(yè)面
【正文】 (j)=max(ve(i) + dut(i,j)) i,j∈ T,T是以 j為頭的弧的集合 v8 v1 V2 V3 v5 v7 v9 Vi到 Vj的最長(zhǎng)路徑 如何求關(guān)鍵路徑 vl(n1)=ve(n1)，然后 按照頂點(diǎn) 逆拓?fù)渑判?后的次序求其余頂點(diǎn)的 vl vl(i)=min(vl(j) dut(i,j)) i,j∈ S,S是以 i為尾的弧的集合 v8 v1 V2 V3 v5 v7 v9 如何求關(guān)鍵路徑 用 e(i)和 l(i)分別表示活動(dòng) ai的最早開(kāi)始間和最遲開(kāi)始時(shí)間 顯然有： 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，說(shuō)明 G中存在環(huán)，算法終止。 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 假設(shè)以 AOE網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需的時(shí)間。} // 對(duì) v的尚未訪問(wèn)的鄰接頂點(diǎn) w遞歸調(diào)用 DFST Push(S, v)。 w=0。 printf(“%d”, v)} } 拓?fù)渑判?方法 2 void DFST(Graph G, int v) { // 從頂點(diǎn) v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 ++v) { if (!visited[v]) DFST(G, v)。//存放頂點(diǎn)，按照出 DFS的次序 for (v=0。 ++v) visited[v] = FALSE。 結(jié)論： 拓?fù)渑判?方法 2 void DFSToplogicalSort (Graph G, int v) {//如何確定 v
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1