有向無環(huán)圖及其應(yīng)用-資料下載頁
2025-10-10 20:28本頁面
【正文】 拓?fù)溆行蚣?逆拓?fù)溆行?的前提下進行。 ? 設(shè) 活動 ak (k=1,2,…, e)在帶權(quán)有向邊 Vi , Vj 上 , 其持續(xù)時間用 dur (Vi , Vj ) 表示 , 則有 e[k] = ve[i]； l[k] = vl[j] dur(Vi , Vj )； k = 1, 2, …, e。這樣就得到計算關(guān)鍵路徑的算法。 ? 為了簡化算法 , 假定在求關(guān)鍵路徑之前已經(jīng)對各頂點實現(xiàn)了拓?fù)渑判?, 并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c重新進行了編號。 ? 對算法 ： （算法 ve） ① 設(shè)初值 ve(i)=0 (0≤ i≤ n1) ② 計算 Vj的直接后繼 Vk的 ve(k)： 若 ve(j)+dut(j,k) ve(k) 則 ve(k)=ve(j)+ dut(j,k) ③ 為求 vl，設(shè)一棧記錄拓?fù)溆行蛐蛄校髲棗Ｇ竽嫱負(fù)溆行蛐蛄? ? 算法 （先求各事件的 vl，再求各活動的 e和 l（ 中用 ee和 el表示），當(dāng)某個活動的 e=l，則該活動是關(guān)鍵活動） 1 3 2 4 a1=8 a2=12 5 6 7 8 a10=12 a9=6 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 Ve Vl 1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58 e l 0 0 8 12 12 22 22 28 40 46 0 0 8 12 12 32 22 28 40 46 1 2 3 4 5 6 7 8 9 10 三條關(guān)鍵路徑： 124578 134578 13678 注意 ?所有頂點按拓?fù)溆行虻拇涡蚓幪? ?僅計算 ve[i] 和 vl[i] 是不夠的，還須計算 e[k] 和 l[k]。 ?不是任一關(guān)鍵活動加速一定能使整個工程提前。 ?想使整個工程提前，要考慮各條關(guān)鍵路徑上所有關(guān)鍵活動。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1