【正文】 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 The End Data Structure 。 ?題目 ?假設(shè)無向圖采用鄰接表結(jié)構(gòu)表示。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?利用 Dijkstra算法求最短路徑 V0 v5 v4 v3 v2 100 60 30 50 20 10 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ v1 10 5 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?利用 Dijkstra算法求最短路徑 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 第 7章作業(yè) ? P258—— P277 ?以下題目做在書本上：、 、 ?以下題目做在習(xí)題本上，必須抄題： 、 、 、 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 實(shí)驗(yàn)八 ?上機(jī)前的預(yù)習(xí) ?在實(shí)驗(yàn)預(yù)習(xí)報告上 編寫好上機(jī)題的源程序 及運(yùn)行程序所需的典型數(shù)據(jù)，并給程序加上適當(dāng)?shù)淖⑨?。所以總的時間復(fù)雜度是 O(n2)。amp。 for(i=1。 //final[v]為 TRUE當(dāng)且僅當(dāng) v∈S ，即已經(jīng)求得從 v0到 v的最短路徑。D){ //用 Dijkstra算法求有向網(wǎng) G的 v0頂點(diǎn)到其余頂點(diǎn) v的最短路徑 P[v]及其帶權(quán)長度 D[v]。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法 ? void ShortestPath_DIJ(MGraph G， int v0， PathMatrix amp。 ? ③ 修改： dist[i]←min{dist[i],dist[k]+Edge[k][i] }, // 對于每一個 i ? V S 。 // n為圖中頂點(diǎn)個數(shù) ? ② 求出最短路徑的長度： dist[k] ← min { dist[i] }, i ? V S 。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法可描述如下： ? ① 初始化： S ← { v0 }。 ?假設(shè) S是已求得的最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑必然是從 v0 出發(fā)，中間只經(jīng)過 S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn) vx(vx?VS )的路徑中的一條。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra逐步求解的過程 1 0 4 3 2 10 100 30 50 20 60 10 源點(diǎn) 終點(diǎn) 最短路徑 路徑長度 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 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra逐步求解的過程 ?引入輔助數(shù)組 dist，其每一個分量 dist[i]表示當(dāng)前找到的從源點(diǎn) v0到終點(diǎn) vi的最短路徑的長度。 ?為求得這些最短路徑 , Dijkstra提出 按路徑長度的遞增次序，逐步產(chǎn)生最短路徑 的算法。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?問題解法 ?邊上權(quán)值非負(fù)情形的單源最短路徑問題 ?Dijkstra算法 （只講此算法） ?邊上權(quán)值為任意值的單源最短路徑問題 ?Bellman和 Ford算法 ?所有頂點(diǎn)之間的最短路徑 ?Floyd算法 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法 ?問題描述 ?給定一個帶權(quán)有向圖 D與源點(diǎn) v，求從 v到 D中其它頂點(diǎn)的最短路徑。 ?考慮到交通圖的有向性 (如航運(yùn)，逆水和順?biāo)畷r的船速就不一樣 )，討論帶權(quán)有向圖，并稱路徑上的第一個頂點(diǎn)為源點(diǎn) (Sourse)，最后一個頂點(diǎn)為終點(diǎn) (Destination)。圖中頂點(diǎn)表示城市，邊表示城市間的交通聯(lián)系。 ?設(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)鍵路徑的算法。 ?從 Vl[n1] = Ve[n1]開始，反向遞推 Vi, Vj ? S1, i = n2, n3, ? ,0 S1是所有源自 Vi的有向邊 Vi , Vj 的集合。 ?為求得 e[k]與 l[k], 需要先求得從源點(diǎn) V0到各個頂點(diǎn) Vi的 Ve[i]和 Vl[i]。 l[k] == e[k] 表示活動 ak是沒有時間余量的關(guān)鍵活動。 l[k] = Vl[j]dur(i, j) 其中 , dur(i,j)是完成 ak所需的時間。 ?活動 ak的 最早可能開始時間 e[k]：設(shè)活動 ak在邊 Vi， Vj上，則 e[k]是從源點(diǎn) V0到頂點(diǎn) Vi的最長路徑長度。 a9=6 1 3 2 4 a1=8 a2=12 5 6 7 8 a10=12 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 關(guān)鍵路徑 ?與計算關(guān)鍵活動有關(guān)的量的定義 ?事件 Vi的 最早可能開始時間 Ve(i)：從源點(diǎn) V0到頂點(diǎn) Vi的最長路徑長度。 ?關(guān)鍵活動 ：關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，因此提前完成非關(guān)鍵活動并不能加快工程的進(jìn)度。 ?完成整個工程至少需要多少時間 ? ?為縮短完成工程所需的時間 , 應(yīng)當(dāng)加快哪些活動 ? a9=6 1 3 2 4 a1=8 a2=12 5 6 7 8 a10=12 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 關(guān)鍵路徑 ?AOE網(wǎng) ?從源點(diǎn)到各個頂點(diǎn) , 以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條，長度也可能不同。 ?AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中，頂點(diǎn)表示事件 (Event)，弧表示活動 (Activity), 權(quán)表示活動持續(xù)的時間 (Duration)。 ? 該算法亦是求關(guān)鍵路徑的基礎(chǔ)。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 拓?fù)渑判? ?拓?fù)渑判蛩惴? ? Status Topological Sort(ALGraph G){ //有向圖 G采用鄰接表存儲結(jié)構(gòu) //若 G無回路，則輸出 G的頂點(diǎn)的 1個拓?fù)湫蛄胁⒎祷?OK，否則ERROR。 ?入度為零的頂點(diǎn)即為沒有前驅(qū)的頂點(diǎn)，刪除頂點(diǎn)及以它為尾的弧的操作，則可換以弧頭頂點(diǎn)的入度減 1來實(shí)現(xiàn)。這時網(wǎng)絡(luò)中必存在有向環(huán)。令 n為頂點(diǎn)個數(shù)； ?② 在 AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點(diǎn)，并輸出之； ?③ 從圖中刪去該頂點(diǎn)，同時刪去所有它發(fā)出的有向邊； ?④ 重復(fù)以上 ②、③步 , 直到： ?全部頂點(diǎn)均已輸出 ，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；? ?圖中還有未輸出的頂點(diǎn) , 但已跳出處理循環(huán) 。 ?如果通過拓?fù)渑判蚰軐?AOV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個拓?fù)溆行虻男蛄兄?, 則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。 ?對給定的 AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán) —— 構(gòu)造它的拓?fù)溆行蛐蛄?，使?AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。 ?在 AOV網(wǎng)中不能出現(xiàn)有向回路，即有向環(huán)。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。 ?實(shí)例：計算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。它或者是一個施工流程圖，或者是一個產(chǎn)品生產(chǎn)的流程圖，再或是一個數(shù)據(jù)流圖 (每個頂點(diǎn)表示一個過程 )。 ?全序： 設(shè) R是集合 X上的偏序 (Partial Order)，如果對每個 x,y∈X 必有 xRy或 yRx，則稱 R是集合 X上的 全序 關(guān)系。 ?對整個工程和系統(tǒng)，人們關(guān)心的是兩個方面的問題： ?工程能否順利進(jìn)行？ ?計算整個工程完成所必須的最短時間？ 拓?fù)渑判? 關(guān)鍵路徑 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 拓?fù)渑判? ?拓?fù)渑判?(Topological Sort) ?拓?fù)渑判颍?由某個集合上的一個偏序得到該集合上的一個全序，這個全序稱為拓?fù)溆行?(Topological Order)。 ?有向無環(huán)圖是描述含有公共子式的表達(dá)式的有效工具 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 ?有向無環(huán)圖 ?表達(dá)式： ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 用二叉樹描述表達(dá)式 描述表達(dá)式的有向無環(huán)圖 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 ?有向無環(huán)圖 ? 描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 A B C D E F G H I J A B C D E F G H J A B C D E F G H J I I 1 2 3 4 5 6 7 8 9 10 根有兩 個子女 關(guān)節(jié)點(diǎn) 關(guān)節(jié)點(diǎn) 關(guān)節(jié)點(diǎn) 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 ?有向無環(huán)圖 (Directed Acycline Graph) ?指一個無環(huán)的有向圖，簡稱 DAG圖。 ?深度優(yōu)先生成樹的根是關(guān)節(jié)點(diǎn)的充要條件是它至少有兩個子女。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?重連通分量 (Biconnected Component) ?在一個無向連通圖 G中 , 重連通分量