【正文】 8 a10=12 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 關(guān)鍵路徑 ?求關(guān)鍵路徑 ?為找出關(guān)鍵活動(dòng) , 要求各個(gè)活動(dòng)的 e[k]與 l[k]，以判別是否： l[k]==e[k]。 ?為求得 e[k]與 l[k], 需要先求得從源點(diǎn) V0到各個(gè)頂點(diǎn) Vi的 Ve[i]和 Vl[i]。 ?求 Ve[i]的遞推公式 ?從 Ve[0] = 0 開始，向前遞推 Vj, Vi ? S2, i = 1, 2, ? , n1 S2 是所有指向 Vi 的有向邊 Vj , Vi 的集合。 ?從 Vl[n1] = Ve[n1]開始，反向遞推 Vi, Vj ? S1, i = n2, n3, ? ,0 S1是所有源自 Vi的有向邊 Vi , Vj 的集合。 }, ) ,(][ {][ ???? ijj VVdu rjVem axiVe}, ) ,(][ {][ ???? jij VVdu rjVlm i niVl南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 關(guān)鍵路徑 ?求關(guān)鍵路徑 ?兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)行。 ?設(shè)活動(dòng) ak(k=1,2,… ,e)在帶權(quán)有向邊 Vi,Vj 上 , 其持續(xù)時(shí)間用 dur(Vi,Vj)表示 , 則有： e[k]=Ve[i]； l[k]=Vl[j]dur(Vi,Vj)； k=1,2,… ,e ?得到計(jì)算關(guān)鍵路徑的算法。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 關(guān)鍵路徑 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 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ì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?問題背景 ?假若要在計(jì)算機(jī)上建立一個(gè)交通咨詢系統(tǒng)則可以采用圖的結(jié)構(gòu)來表示實(shí)際的交通網(wǎng)絡(luò)。圖中頂點(diǎn)表示城市，邊表示城市間的交通聯(lián)系。這個(gè)咨詢系統(tǒng)可以回答旅客提出的各種問題。 ?考慮到交通圖的有向性 (如航運(yùn)，逆水和順?biāo)畷r(shí)的船速就不一樣 )，討論帶權(quán)有向圖，并稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn) (Sourse)，最后一個(gè)頂點(diǎn)為終點(diǎn) (Destination)。 ?最短路徑問題： 如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）出發(fā)到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權(quán)值總和達(dá)到最小。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?問題解法 ?邊上權(quán)值非負(fù)情形的單源最短路徑問題 ?Dijkstra算法 （只講此算法） ?邊上權(quán)值為任意值的單源最短路徑問題 ?Bellman和 Ford算法 ?所有頂點(diǎn)之間的最短路徑 ?Floyd算法 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法 ?問題描述 ?給定一個(gè)帶權(quán)有向圖 D與源點(diǎn) v，求從 v到 D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于 0。 ?為求得這些最短路徑 , Dijkstra提出 按路徑長度的遞增次序，逐步產(chǎn)生最短路徑 的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn) v到其它各頂點(diǎn)的最短路徑全部求出為止。 南昌航空大學(xué)計(jì)算機(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ì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra逐步求解的過程 ?引入輔助數(shù)組 dist，其每一個(gè)分量 dist[i]表示當(dāng)前找到的從源點(diǎn) v0到終點(diǎn) vi的最短路徑的長度。初始狀態(tài)： ?若從源點(diǎn) v0到頂點(diǎn) vi 有邊 , 則 dist[i]為該邊上的權(quán)值； ?若從源點(diǎn) v0到頂點(diǎn) vi 無邊 , 則 dist[i]為 ? 。 ?假設(shè) S是已求得的最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑必然是從 v0 出發(fā)，中間只經(jīng)過 S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn) vx(vx?VS )的路徑中的一條。 ?每次求得一條最短路徑后，其終點(diǎn) vk加入集合 S，然后對所有的 vi?VS，修改其 dist[i]值。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法可描述如下： ? ① 初始化： S ← { v0 }。 dist[j] ← Edge[0][j], j = 1, 2, … , n1。 // n為圖中頂點(diǎn)個(gè)數(shù) ? ② 求出最短路徑的長度： dist[k] ← min { dist[i] }, i ? V S 。 S ← S U { k }。 ? ③ 修改： dist[i]←min{dist[i],dist[k]+Edge[k][i] }, // 對于每一個(gè) i ? V S 。 ? ④ 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) ②。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法 ? void ShortestPath_DIJ(MGraph G， int v0， PathMatrix amp。P，ShortPathTable amp。D){ //用 Dijkstra算法求有向網(wǎng) G的 v0頂點(diǎn)到其余頂點(diǎn) v的最短路徑 P[v]及其帶權(quán)長度 D[v]。 //若 P[v][w]為 TRUE，則 w是從 v0到 v當(dāng)前求得最短路徑上的頂點(diǎn)。 //final[v]為 TRUE當(dāng)且僅當(dāng) v∈S ，即已經(jīng)求得從 v0到 v的最短路徑。 for(v=0； v； ++v) { final[v]=FALSE； D[v]=[v0][v]； for(w=0； w； ++w) P[v][w] = FALSE； //設(shè)空路徑 if (D[v]INFINITY) { P[v][v0]=TRUE； P[v][v]=TRUE； } }//for 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法 ? D[v0] = 0； final[v0] = TRUE； //初始化， v0頂點(diǎn)屬于 S集 //開始主循環(huán)，每次求得 v0到某個(gè) v頂點(diǎn)的最短路徑，并加 v到 s集。 for(i=1。 i； ++i){ //其余 min = INFINITY； //當(dāng)前所知離 v0頂點(diǎn)的最近距離 for(w=0； w； ++w) if(!final[w]) //w頂點(diǎn)在 VS中 if(D[w]min){v=w； min=D[w]； } //w頂點(diǎn)離 v0頂點(diǎn)更近 final[v]=TRUE； //離 v0頂點(diǎn)最近的 v加入 S集 for(w=0； w； ++w) //更新當(dāng)前最短路徑及距離 if(!final[w]amp。amp。(min+[v][w]D[w])){ //修改 D[w]和 P[w] D[w]=min+[v][w]； P[w]=P[v]； P[w][w]=TRUE； //P[w]=P[v]+[w] }//if }//for }//ShortestPath_DIJ 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?Dijkstra算法分析 ?第一個(gè) FOR循環(huán)的時(shí)間復(fù)雜度是 O(n)，第二個(gè) FOR循環(huán)共進(jìn)行 n1次，每次執(zhí)行的時(shí)間是 O(n)。所以總的時(shí)間復(fù)雜度是 O(n2)。人們可能只希望找到從源點(diǎn)到某一個(gè)特定的終點(diǎn)的最短路徑，但是，這個(gè)問題和求源點(diǎn)到其它所有頂點(diǎn)的最短路徑一樣復(fù)雜，其時(shí)間復(fù)雜度也是 O(n2) 。 南昌航空大學(xué)計(jì)算機(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ì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 最短路徑 ?利用 Dijkstra算法求最短路徑 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 第 7章作業(yè) ? P258—— P277 ?以下題目做在書本上：、 、 ?以下題目做在習(xí)題本上，必須抄題： 、 、 、 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 實(shí)驗(yàn)八 ?上機(jī)前的預(yù)習(xí) ?在實(shí)驗(yàn)預(yù)習(xí)報(bào)告上 編寫好上機(jī)題的源程序 及運(yùn)行程序所需的典型數(shù)據(jù)，并給程序加上適當(dāng)?shù)淖⑨尅３绦蚣由线m當(dāng)?shù)淖⑨尅? ?題目 ?假設(shè)無向圖采用鄰接表結(jié)構(gòu)表示。編程分別實(shí)現(xiàn)圖的深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 The End Data Structure