7第七章-圖(參考版)
2025-07-27 10:05本頁面
【正文】 在上述 n+1步中 ， D的值不斷變化 ， 對應(yīng)一個 n階方陣序列 。 …… 依此類推 ， 經(jīng)過 n次比較和修正 ， 在第 （ n1） 步 ， 將求得 vi到 vj 的且中間頂點號不大于 n1的最短路徑 ， 這必是從 vi到 vj的最短路徑 。 （ 2） 在 vi、 vj間加入頂點 v2， 得 （ vi, …, v2） 和 (v2, …, vj)， 其中（ vi, …, v2） 是 vi到 v2 的且中間頂點號不大于 1的最短路徑 ， (v2, …, vj) 是 v2到 vj 的且中間頂點號不大于 1的最短路徑 ， 這兩條路徑在上一步中已求出 。 （ 1） 在 vi、 vj間加入頂點 v1， 得 （ vi, …， v1） 和 (v1, …， vj)， 其中 （ vi, …, v1） 是 vi到 v1 的且中間頂點號不大于 0的最短路徑 ， (v1, …, vj) 是 v1到 vj 的且中間頂點號不大于 0的最短路徑 ， 這兩條路徑在上一步中已求出 。 ? 舉例說明 Dijkstra逐步求解的過程 1 0 4 3 2 10 100 30 50 20 60 10 源點 終點 最短路徑 路徑長度 v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2) ?,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100, 90,60 求任意一對頂點間的最短路徑 1. 弗羅伊德算法的基本思想如下： 設(shè)圖 g用鄰接矩陣法表示 ， 求圖 g中任意一對頂點 vi、 vj間的最短路徑 。 ? 為求得這些最短路徑 , Dijkstra提出按路徑長度的遞增次序 , 逐步產(chǎn)生最短路徑的算法。 ? 問題解法 ? 邊上權(quán)值非負情形的單源最短路徑問題 — Dijkstra算法 ? 所有頂點之間的最短路徑 — Floyd算法 邊上權(quán)值非負情形的單源最短路徑問題 ? 問題的提法： 給定一個帶權(quán)有向圖 D與源點 v，求從 v 到 D中其它頂點的最短路徑。 ?想使整個工程提前，要考慮各個關(guān)鍵路徑上所有關(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 注意 ?所有頂點按拓撲有序的次序編號 ?僅計算 Ve[i] 和 Vl[i] 是不夠的，還須計算 e[k] 和 l[k]。 這樣就得到計算關(guān)鍵路徑的算法。 }, ) ,(][ {][ ???? ijjVVdu rjVem axiVe}, ) ,(][ {][ ???? jijVVdu rjVlm i niVl ? 這兩個遞推公式的計算必須分別在拓撲有序及逆拓撲有序的前提下進行。 ? 求 Ve[i]的遞推公式 ? 從 Ve[0] = 0 開始，向前遞推 Vj, Vi ? S2, i = 1, 2, ? , n1 S2 是所有指向 Vi 的有向邊 Vj , Vi 的集合。 ? 為找出關(guān)鍵活動 , 需要求各個活動的 e[k] 與 l[k]，以判別是否 l[k] == e[k]。 ⑤ 時間余量 l[k] e[k] 表示活動 ak 的最早可能開始時間和最遲允許開始時間的時間余量。 l[k] = Vl[j] dur(i, j)。 因此 , e[k] = Ve[i]。 ② 事件 Vi 的最遲允許開始時間 Vl[i] 是在保證匯點 Vn1 在 Ve[n1] 時刻完成的前提下 ， 事件 Vi 的允許的最遲開始時間 。 ? 構(gòu)成關(guān)鍵路徑的弧即為 關(guān)鍵活動 。 (h) 拓撲排序完成 AOV網(wǎng)絡(luò)及其鄰接表表示 C0 C1 C2 C3 C4 C5 C0 C1 C2 C3 0 C4 C5 0 0 1 2 3 4 5 count data adj 1 3 0 1 0 3 1 dest link 3 0 5 1 5 0 0 1 5 0 關(guān)鍵路徑 AOE網(wǎng)（ Activity On Edge）是用邊表示活動的網(wǎng)絡(luò) ? 帶權(quán)的有向無環(huán)圖 ? 頂點表示事件、弧表示活動，權(quán)表示活動持續(xù)的時間 ? 可用來估算工程的完成時間 關(guān)鍵路徑 ? 在 AOE網(wǎng)絡(luò)中，一條路徑上各弧權(quán)值之和稱為該路徑的 帶權(quán)路徑長度 。 C0 C1 C2 C3 C4 C5 拓撲排序的過程 (a) 有向無環(huán)圖 C2 C5 C1 C0 C3 (b) 輸出頂點 C4 C1 C2 C5 C3 (c) 輸出頂點 C0 C4 C0 C2 C5 C1 C3 (d) 輸出頂點 C3 C1 C2 C5 (e
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1