信息學 圖論最短路徑

1、圖的最短路徑教學專題圖的最短路徑授課學時1學時（約50分鐘）教學課型新授課授課對象冬令營A層次教學內(nèi)容和教學目標知識點學習要求了解理解掌握最短路徑問題的描述無權(quán)圖最短路徑單源最短路徑(邊權(quán)值非負)Dijkstra算法中貪心策略Dijkstra算法優(yōu)化任意頂點對間最短路徑Floyd算法中動態(tài)規(guī)劃思想圖的傳遞閉包教學重點有權(quán)圖最短路徑教學難點Dijkstra算法設(shè)計過程（用flash動畫模擬突破難點）教學流程知識點時間分配最短路徑問題的引入2分鐘無權(quán)圖最短路徑5分鐘單源最短路徑(邊權(quán)值非負)15分鐘交互討論：邊權(quán)值為負時Dijkstra的局限性及改進5分鐘任意頂點對間最短路徑15分鐘圖的傳遞閉包5

2、分鐘媒體使用多媒體課件：動畫模擬最短路徑求解過程教學內(nèi)容及示例設(shè)計意圖目前，互聯(lián)網(wǎng)上有許多網(wǎng)站可用來查找兩個地理之間的通路，例如，Google 地圖，Baidu 地圖等，這些路徑查找系統(tǒng)都是用抽象表示國道或省市間的公路，圖中的節(jié)點表示城市，圖中邊表示公路路段，邊權(quán)值表示城市之間的距離，當然也可以表示從某地出發(fā)到達目標的時間。例如，從蘇州到南京的司機最關(guān)心的是：（1） 蘇州、南京之間存在通路嗎？（2） 如果蘇州、南京之間有一條以上通路，哪條路最短？目前，第一個問題我們有解決的辦法，采用深度優(yōu)先搜索或者廣度優(yōu)先搜索遍歷圖可以達到目的，本節(jié)課我們還將討論其他算法。第二個問題是本節(jié)重點討論的，雖然我們

3、可以枚舉任一條可能路徑，然后檢查是否為最短，但是幾乎需要n！的時間，效率太低，我們需要更有效的。一、無權(quán)圖最短路徑例1：如下圖，假設(shè)C1,C2,C3,C4,C5,C6是六座城市，他們之間的連線表示兩城市間有道路相通，如果在每一個城市均需要換乘一次飛機，問從C1到其余各城市最少換乘次數(shù)。圖1 六個城市地圖對于圖G=（V，E），頂點集合V和邊集合E，邊<Ci,Cj>沒有賦權(quán)值，或者也可以認為權(quán)值均為1，Ci,j=1，一條路徑C1，C2上的邊數(shù)叫做無權(quán)路徑長度（Unweighted path length）找出從C1出發(fā)到其余各點的最短路徑。因為邊是沒有賦權(quán)的，所以只對邊的數(shù)目感興趣，如

4、果需要記錄實際路徑我們可以增加一個變量path來代表路徑就可以了。此時此刻可以說從C1到C1（它本身）的最短路徑是長為0的路徑，把這個信息做個標記，得到下圖：圖2 C1被訪問然后開始尋找所有與C1相連的頂點，它們與C1的距離為1，此時我們可以看到C2、C3與C1僅有“一邊之遙”，把它們表示在下圖，圖3 C1被訪問后對鄰居頂點的影響以此推斷，到算法結(jié)束，分別如下圖所示：圖4 最短路徑圖顯然這種搜索方式就是大家學過的圖的廣（寬）度優(yōu)先搜索（Breadth-first search），該方法按層次處理頂點：距開始點最近的頂點首先被訪問到，而最遠的點最后被訪問。偽代碼如下：用鄰接矩陣存儲圖/ 無權(quán)最短

5、路徑/ 輸入：圖的鄰接矩陣ga，源點i/ 輸出：源點i至圖其它各點的最短路徑path（需逆向追溯路徑）和長度distprocedure shortest_unweighted(i:integer);begin disti := 0; 其它dist為一個非常大的值代表不可達； pathi :=0; / 0代表是起點或者訪問不到；path記錄由哪一點訪問它 頂點i 進入隊列 Q； while 隊列Q 非空 dobegin 從隊列Q中取出隊首元素v； knownv := true; for j := 1 to n do / 依次訪問v的所有可直達頂點 begin if ( not knownj )

6、and ( gav,j =1 ) then begin if distj 為非常大的值then distj := distv + 1; pathj := v; 頂點j 進入隊列Q； end; / end of then end ; / end of for end; / end of while end; / end of shortest_unweithted對于每個頂點，我們追蹤了三個信息：是否被訪問過？距起點的距離是多少，由哪個頂點去訪問它下面的一組表格顯示追蹤過程：注意最開始dist的值均為非常大的值 表 1 追蹤過程鑒于兩個對頂點集合的循環(huán)，該算法的的時間復(fù)雜度為O（|V|2）效率較

7、低，這是因為在內(nèi)部循環(huán)中，盡管所有頂點早就known了，但是循環(huán)還要繼續(xù)下去。請大家思考優(yōu)化方法（提示：使用鄰接表存儲）?？茨芊駜?yōu)化到O（|V| + |E|），對于邊信息較少的圖有很大的速度提升。如果圖是賦權(quán)圖，那么問題就明顯地變得困難了，這是因為每個點的重要性不僅僅局限于離起點的遠近，而跟它提供的邊的權(quán)值的有關(guān)。不過我們?nèi)匀豢梢允褂脕碜詿o權(quán)情形時的想法。請看下面的討論二、單源最短路徑（從一個頂點到其余各頂點的最短路徑，邊的權(quán)值為非負）例2：如下圖，假設(shè)C1,C2,C3,C4,C5,C6是六座城市，他們之間的連線表示兩城市間有道路相通，連線旁的數(shù)字表示路程。請編寫一程序，找出C1到Ci的最短路

8、徑(2i6)，輸出路徑序列及最短路徑的路程長度。圖5 賦權(quán)六城市地圖問題分析下面給出解決這個問題的Dijkstra算法思想。 Dijkstra算法像無權(quán)最短路徑算法一樣，按階段進行。在每個階段，Dijkstra算法選擇一個頂點Cm，頂點Cm須滿足它在所有未訪問頂點中具有最小的distm,同時算法聲明從Ci到Cm的最短路徑是已知的。階段的其余部分由其它頂點j的dist值的更新工作組成。區(qū)別在于：在無權(quán)的情形中，若distj=非常大的值（如maxint），則distj=distm+1，而賦權(quán)的情形，如果當distj的新值distm + GAm,j是個更好的改進值，我們就讓distj=distm +

9、 GAm,j，即distj= Mindistj,distm+GAm,j，這是一次松弛操作。簡而言之，在通向j路徑時，是否使用頂點m由算法來判斷。當然原始的distj是沒有用到distm的值的。Dijkstra算法瞬間執(zhí)行圖：下一步選擇頂點x圖6 通過u到達未訪問頂點序列中的x路徑最短具體算法思路如下：設(shè)圖G用鄰接矩陣的方式存儲在GA中，GAi,j=maxint表示Ci，Cj是不關(guān)聯(lián)的，否則為權(quán)值（非負值）。設(shè)集合S用來保存已求得最短路徑的終點序號，初始時S=Ci表示只有源點，以后每求出一個終點Cj，就把它加入到集合中并作為新考慮的中間頂點。設(shè)數(shù)組dist1.n用來存儲當前求得的最短路徑，初始時

10、Ci，Cj如果是關(guān)聯(lián)的，則distj等于權(quán)值，否則等于maxint，以后隨著新考慮的中間頂點越來越多，distj可能越來越小。再設(shè)一個與dist對應(yīng)的數(shù)組path1.n用來存放當前最短路徑的邊，初始時為Ci到Cj的邊，如果不存在邊則為空。執(zhí)行時，先從S以外的頂點（即待求出最短路徑的終點）所對應(yīng)的dist數(shù)組元素中，找出其值最小的元素（假設(shè)為distm），該元素值就是從源點Ci到終點Cm的最短路徑長度，對應(yīng)的pathm中的頂點或邊的序列即為最短路徑。接著把Cm并入集合S中，然后以Cm作為新考慮的中間頂點，對S以外的每個頂點Cj，比較distm+GAm,j的distj的大小，若前者小，表明加入了新

11、的中間頂點后可以得到更好的方案，即可求得更短的路徑，則用它代替distj，同時把Cj或邊（Cm，Cj）并入到pathj中。從某一個頂點Ci到其余任一頂點Cj的最短路徑，可能是它們之間的邊（Ci，Cj），也可能是經(jīng)過k個中間頂點即k+1條邊所形成的路徑(1kn-2)。重復(fù)以上過程n-2次，即可在dist數(shù)組中得到從源點到其余各終點的最段路徑長度，對應(yīng)的path數(shù)組中保存著相應(yīng)的最段路徑。對于上圖，采用Dijkstra算法找出C1到Cj之間的最短路徑(2j6)的過程如下：初始時： 表2 初始選擇C1123456S100000Dist048maxintmaxintmaxintPathC1C1,C2C

12、1,C3第一次：選擇m=2，則S=C1,C2，計算比較dist2+GA2,j與distj的大小 表3 選擇C2123456S110000Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：選擇m=3，則S=C1,C2,C3，計算比較dist3+GA3,j與distj的大小 表4 選擇C3123456S111000Dist04789maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5第三次：選擇m=4，S=C1,C2,C3,C4，計算比較dist4+GA4,j與distj的大小 表5 選擇C412345

13、6S111100Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6第四次：選擇m=5，則S=C1,C2,C3,C4,C5，計算比較dist5+GA5,j與distj的大小 表6 選擇C5123456S111110Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因為該圖的度n=6，所以執(zhí)行n-2=4次后結(jié)束，最后一個頂點C6如果dist不是maxint，代表有路徑，它是不需要探索的。表7 C6為最后頂點123456S111111Dist0478913

14、PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6此時通過dist和path數(shù)組可以看出：C1到C2的最短路徑為：C1C2，長度為：4；C1到C3的最短路徑為：C1C2C3，長度為：7；C1到C4的最短路徑為：C1C2C4，長度為：8；C1到C5的最短路徑為：C1C2C3C5，長度為：9；C1到C6的最短路徑為：C1C2C3C5C6，長度為：13；下面給出具體的Dijkstra算法框架（注：為了實現(xiàn)上的方便，我們用一個一維數(shù)組s1.n代替集合S，用來保存已求得最短路徑的終點集合，即如果sj=0表示頂點Vj不在集合中，反之，sj=1表示頂點V

15、j已在集合中）。主要代碼如下：/ 無向有權(quán)圖單源最短路徑/ 輸入：圖的鄰接矩陣ga，源點i/ 輸出：源點i至圖其它各點的最短路徑path和長度distProcedure Dijkstra(GA,dist,path,i)； 表示求Vi到圖G中其余頂點的最短路徑，GA為圖G的鄰接矩陣，dist和path為變量型參數(shù)，其中path的基類型為集合BeginFor j:=1 To n Do Begin 初始化 If j<>i Then sj:=0 Else sj:=1； distj:=GAi,j； If distj<maxint maxint為假設(shè)的一個足夠大的數(shù) Then pathj

16、:=i+jElse pathj:= ； End；For k:=1 To n-2 Do Begin w:=maxint；m:=i； For j:=1 To n Do 求出第k個終點Cm If (sj=0) and (distj<w) Then Begin m:=j；w:=distj； End； If m<>i Then sm:=1 else exit；若條件成立，則把Cm加入到S中，否則退出循環(huán)，因為剩余的終點，其最短路徑長度均為maxint，無需再計算下去 For j:=1 To n Do 對sj=0的更優(yōu)元素作必要修改 If (sj=0) and (distm+GAm,j&

17、lt;distj) Then Begin Distj:=distm+GAm,j；pathj:=pathm+j； End； End；End；請注意，圖的鄰接矩陣存儲中，GAI,j存放邊<I,j>的值，如果邊不在圖中出現(xiàn)，我們賦予GAI,j一個數(shù)值很大的數(shù)。這個大數(shù)可任選，但需要注意：1）該數(shù)值應(yīng)大于代價矩陣的最大值2）該數(shù)值不應(yīng)該distm+GAm,j的語句溢出。我們來分析一下Dijkstra算法的時間復(fù)雜度，對于有n個頂點的圖，其復(fù)雜度為O（n2）當然如果我們選擇更好的數(shù)據(jù)結(jié)構(gòu)如用鄰接表存儲圖結(jié)構(gòu)，在選擇m結(jié)點檢查distm時采用優(yōu)先隊列那么時間復(fù)雜度可以在O(nlogn)時間內(nèi)，

18、同學們?nèi)绻信d趣可以去查閱相關(guān)書籍。另外我們要指出的Dijkstra算法，是20世紀中期，Edsger Dijkstra提出的一個非常簡單、有效的貪心算法來求解單源最短路徑問題。它實際上是一個用于圖遍歷的廣度優(yōu)先搜索算法的一個“拓展”版本，它每次都選擇了一個“領(lǐng)先的”結(jié)點。它的出現(xiàn)可能源于下面的生活常識：假設(shè)G的邊構(gòu)成一個充滿水的管道系統(tǒng)，這個管道在結(jié)點處相交，每條邊有一定的長度，現(xiàn)在假設(shè)在結(jié)點S處攪動一下水，并且從S開始引起一個波動。當這個波動以常數(shù)速度向外傳播時，波面擴張按照它們到S的距離增加的順序到達結(jié)點。一個事實：波面到達任意結(jié)點V所走的路徑恰好是一條最短路徑。對于有向無環(huán)圖（DAG）

19、同樣可以采用上述算法來求單源最短路徑，但是如果邊權(quán)出現(xiàn)負值將無法使用Dijkstra算法，請看下例？使用Dijkstra算法，得到1->3的最短路徑為1，而實際上是0。一個誘人的方案是將一個常數(shù)加到們每一條邊的權(quán)值上，如此除去負的邊，再計算新圖的最短路徑問題，然后把結(jié)果減去常數(shù)后用到原來的圖上。這種方案不可能直接實現(xiàn)，因為路徑有可能發(fā)生變化或者，那些有許多條邊的路徑變得比那些具有很少條邊的路徑權(quán)值和更重了。如下圖 每條邊都加上一個正數(shù)2邊權(quán)值 + 2圖 7 有負權(quán)邊對Dijkstra算法影響問題出在哪里？Dijkstra算法中頂點3先于2被聲明為已經(jīng)訪問過的定點，1到3的路徑不會發(fā)生變化

20、，但此時恰好存在了一條可以從未訪問的頂點2回到3的負權(quán)邊，這就有可能導致路徑1->2->3比1->3更短，盡管路徑1->2比1->3長。這表明了一條路徑可以從“昂貴”的邊開始，然后接著用“負費用”的邊進行補償，Dijkstra風格的貪心方法在這里不起作用。下面我們來看一種既可以解決邊權(quán)為負，且可以同時求得任一對頂點間最短路徑的算法。三、Floyd算法例3：以例2圖為例，求任意一對頂點之間的最短路徑。問題分析這個問題的解法有兩種：一是分別以圖中的每個頂點為源點共調(diào)用n次Dijkstra算法，這種算法的時間復(fù)雜度為O（n3）；另外還有一種算法：Floyd算法，它的思路

21、簡單，但時間復(fù)雜度仍然為O（n3），下面介紹Floyd算法。帶權(quán)圖G的鄰接矩陣用GA表示，再設(shè)一個與GA同類型的表示每對頂點之間最短路徑長度的二維數(shù)組D，D的初值等于GA。這是因為，如果不允許使用任何中間頂點，Ci到Cj的距離就是GAI,j。令DkI,j表示從Ci到Cj的最短路徑，路徑中的中間頂點編號不大于k。特別地D的初值記為D0I,j。算法從矩陣D0開始，隨后一步一步計算D1,D2,D3,Dn。如果已經(jīng)得到了Dk-1,接下來計算Dk的方法需要考慮一下兩種可能情況：1）對任意一對頂點Ci、Cj，從Ci到Cj且中間頂點編號不大于k的最短路徑，如果中間沒有頂點編號為k的頂點，那么路徑長度就是Dk

22、-1I,j（當然有可能是無路徑的）。2）如果上述那條從Ci到Cj的最短路徑中包括頂點編號為k的頂點，那么路徑一定是一條從Ci到Ck的最短路徑再接著一條從Ck到Cj的最短路徑，而且這兩條子路徑中都不含頂點編號大于k-1的頂點，因而它們的長度分別是Dk-1I,k,Dk-1k,j。公式：DkI,j=Min Dk-1I,j，Dk-1I,k + Dk-1k,j, 1kn邊界條件D0I,j=GAI,j，（不經(jīng)過任何一個頂點時路徑長度）這是動態(tài)規(guī)劃技術(shù)典型的應(yīng)用之一。Floyd算法需要在D上進行n次運算，每次以Ck（1kn）作為新考慮的中間點，求出每對頂點之間的當前最短路徑長度，依次運算后，D中的每個元素D

23、i，j就是圖G中從頂點Ci到頂點Cj的最短路徑長度。再設(shè)一個二維數(shù)組P1.n,1.n，記錄最短路徑，其元素類型為集合類型（注意有向圖中此數(shù)組中只記錄了包含頂點）。Floyd算法的具體描述如下：/無向有權(quán)圖任一頂點對間最短路徑/ 輸入：圖的鄰接矩陣ga，源點i/ 輸出：任意頂點間的最短路徑path和長度distProcedure Floyd(GA，D，P)； Begin For i:=1 To n Do 初始化 For j:=1 To n Do Begin Di,j:=GAi,j； If Di,j<maxint Then pi,j:=i+jElse pi,j:= ； End； For k:

24、=1 To n Do 枚舉n個頂點 For i:=1 To n Do For j:=1 To n Do Begin If (i=k)or(j=k)or(i=j) Then Continue； 重復(fù)點無需計算，直接進入下一輪循環(huán) If Di,k+Dk,j<Di,j Then Begin 更新最短路徑長度，并保存 Di,j：= Di,k+Dk,j； Pi,j：= Pi,k+Pk,j； End； End； End；運用Floyd算法，找出任意一對頂點之間的最短路徑及其長度。過程如下表格8 Floyd算法執(zhí)行過程表格9 Dijkstra算法和Floyd算法比較算法名稱解決問題算法思想時間復(fù)雜度編

25、碼復(fù)雜度使用限制優(yōu)化Dijkstra單源最短路徑貪心O（n2）復(fù)雜邊權(quán)非負優(yōu)先隊列斐波那契堆Floyd任一點對最短路徑動態(tài)規(guī)劃O（n3）簡單邊權(quán)可為負（無負環(huán)）但有時，我們可能只是需要了解在圖G中是否存在頂點i到頂點j的路徑，這個問題稱為圖的傳遞閉包問題。四、傳遞閉包圖的傳遞閉包主要用于計算圖的連通性和圖中滿足條件的連通分支。在一張圖中，如何判別任兩個頂點之間是否有路，我們介紹一個跟Floyd算法同樣思想的Warshall算法。其思想是通過一系列n階布爾矩陣來構(gòu)造一個給定的n階頂點圖的傳遞閉包。R0,R1,Rk-1,Rk,Rn這一系列矩陣從R0開始，R0不允許它的路徑中包含任何中間頂點，所以R

26、0就是圖的鄰接矩陣。Rk表示中間頂點編號不大于k的矩陣。如何從矩陣Rk-1的元素生成矩陣Rk的元素，有下面的公式：Rki,j=Rk-1i,j or Rk-1i,j and Rk-1i,j這就表明：如果一個元素Rk-1i,j是1，那么Rki,j也是1 如果一個元素Rk-1i,j是0，當且僅當矩陣中第i行第k列的元素和第k行第j列的元素都是1，該元素在Rki,j才會變成1用下面的圖8所示：圖8 傳遞閉包矩陣圖算法實現(xiàn)時只需要把Floyd算法中路徑的加法計算，改為邏輯運算即可。五、推薦實例：1)求圖9 中帶權(quán)有向圖中每一對頂點間最短路徑。（兩種方法） 拓展1：把V2到V0的邊權(quán)值改為-3，求最短路徑 拓展2：在拓展1的基礎(chǔ)上，將V1到V2的邊權(quán)值改為-2，能否求出最短路徑（提出負環(huán)問題） 圖 9 帶權(quán)有向圖2）上海世界博覽會志愿者問題描述：雖然上海在世界博覽會國家展館之間修筑了天橋，但來到這里的游客還是喜歡走上海世博會的街道，他們總是想知道某兩個展館之間的最短距離，于是志愿者專門回答游客的這個問題，但是由于他們也不可能把這些信息完全記下來，所以總是要向總部詢問。你能勝任這個工作嗎？輸入：第一行兩個數(shù)n,m（1n100,1m500）表示一共有n個體育館，有m條詢問。接下來一個n*n的矩陣，其中第i行第