最短路徑問題的求解

1、最短路徑問題的求解最短路徑問題的求解 最短路徑是圖論中的一個重要問題，具有很高的實用價值，也是信息最短路徑是圖論中的一個重要問題，具有很高的實用價值，也是信息學競賽中常見的一類中等難度的題目，這類問題很能聯(lián)系實際，考察學生學競賽中常見的一類中等難度的題目，這類問題很能聯(lián)系實際，考察學生的建模能力，反映出學生的創(chuàng)造性思維，因為有些看似跟最短路徑毫無關的建模能力，反映出學生的創(chuàng)造性思維，因為有些看似跟最短路徑毫無關系的問題，也可以歸結為最短路徑問題來求解。系的問題，也可以歸結為最短路徑問題來求解。 在帶權圖在帶權圖G=G=（V V，E E）中，若頂點）中，若頂點 Vi,VjVi,Vj是圖是圖G G

2、的兩個頂點，從頂點的兩個頂點，從頂點ViVi到到VjVj的路徑長度定義為路徑上各條邊的權值之和。從頂點的路徑長度定義為路徑上各條邊的權值之和。從頂點ViVi到到VjVj可能有多可能有多條路徑，其中路徑長度最小的一條路徑稱為頂點條路徑，其中路徑長度最小的一條路徑稱為頂點ViVi到到VjVj的最短路徑。的最短路徑。 一般有兩類最短路徑問題：一類是求從某個頂點（源點）到其它頂一般有兩類最短路徑問題：一類是求從某個頂點（源點）到其它頂點（終點）的最短路徑；另一類是求圖中每一對頂點間的最短路徑。點（終點）的最短路徑；另一類是求圖中每一對頂點間的最短路徑。 對于不帶權的圖，只要人為的把每條邊加上權值對于不

3、帶權的圖，只要人為的把每條邊加上權值1 1，即可當作帶權圖，即可當作帶權圖一樣處理了。一樣處理了。 最短路徑問題的求解最短路徑問題的求解 例例1 1、假設、假設A A、B B、C C、D D、E E各個城市之間旅費如下圖紅各個城市之間旅費如下圖紅色數字所示。某人想從城市色數字所示。某人想從城市A A出發(fā)出發(fā)游覽各城市一遍游覽各城市一遍，而所用而所用旅費最少旅費最少，試編程輸出結果。，試編程輸出結果。 問題分析問題分析 解這類問題時，很多同學往往不得要領，采用窮解這類問題時，很多同學往往不得要領，采用窮舉法把所有可能的情況全部列出，再找出其中旅費最舉法把所有可能的情況全部列出，再找出其中旅費最少

4、的那條路徑；或者采用遞歸（深搜）找出所有路徑，少的那條路徑；或者采用遞歸（深搜）找出所有路徑，再找出旅費最少的那條。但這兩種方法都是費時非常再找出旅費最少的那條。但這兩種方法都是費時非常多的解法，如果城市數目多的話則很可能要超時了。多的解法，如果城市數目多的話則很可能要超時了。實際上我們知道，遞歸（深搜）之類的算法一般實際上我們知道，遞歸（深搜）之類的算法一般用于求所有解問題（例如求從用于求所有解問題（例如求從A A出發(fā)每個城市都要走出發(fā)每個城市都要走一遍一共有哪幾種走法？），所以這些算法對于求最一遍一共有哪幾種走法？），所以這些算法對于求最短路徑這類最優(yōu)解問題顯然是不合適的。短路徑這類最優(yōu)解

5、問題顯然是不合適的。 首先，對于這類圖，我們都應該先建立一個鄰接矩陣，存放首先，對于這類圖，我們都應該先建立一個鄰接矩陣，存放任意兩點間的數據（如距離、費用、時間等），以便在程序中方任意兩點間的數據（如距離、費用、時間等），以便在程序中方便調用，以下介紹幾種常見的、更好的求最短路徑問題的算法。便調用，以下介紹幾種常見的、更好的求最短路徑問題的算法。 最短路徑問題的求解最短路徑問題的求解 一、一、 寬度優(yōu)先搜索寬度優(yōu)先搜索寬搜也并不是解決這類問題的優(yōu)秀算法，這里只是簡單介紹一下算法思路，為寬搜也并不是解決這類問題的優(yōu)秀算法，這里只是簡單介紹一下算法思路，為后面的優(yōu)秀算法做個鋪墊。具體如下：后面的

6、優(yōu)秀算法做個鋪墊。具體如下：1 1、 從從A A點開始依次展開得到點開始依次展開得到ABAB、ACAC、ADAD、AEAE四個新結點（第二層結點），當然四個新結點（第二層結點），當然每個新結點要記錄下其旅費；每個新結點要記錄下其旅費；2 2、 再次由再次由ABAB展開得到展開得到ABCABC、ABDABD、ABEABE三個新結點（第三層結點），而由三個新結點（第三層結點），而由ACAC結點結點可展開得到可展開得到ACBACB、ACDACD、ACEACE三個新結點，自然由三個新結點，自然由ADAD可以展開得到可以展開得到ADBADB、ADCADC、ADEADE，由，由AEAE可以展開得到可以展開

7、得到AEBAEB、AECAEC、AEDAED等新結點，對于每個結點也須記錄下其旅費；等新結點，對于每個結點也須記錄下其旅費；3 3、 再把第三層結點全部展開，得到所有的第四層結點：再把第三層結點全部展開，得到所有的第四層結點：ABCDABCD、ABCEABCE、ABDCABDC、ABDEABDE、ABECABEC、ABEDABED、AEDBAEDB、AEDCAEDC，每個結點也需記錄下其旅費；，每個結點也需記錄下其旅費；4 4、 再把第四層結點全部展開，得到所有的第五層結點：再把第四層結點全部展開，得到所有的第五層結點：ABCDEABCDE、ABCEDABCED、AEDBCAEDBC、AEDC

8、BAEDCB，每個結點也需記錄下其旅費；，每個結點也需記錄下其旅費；5 5、 到此，所有可能的結點均已展開，而第五層結點中旅費最少的那個就是題到此，所有可能的結點均已展開，而第五層結點中旅費最少的那個就是題目的解了。目的解了。由上可見，這種算法也是把所有的可能路徑都列出來，再從中找出旅費最少的由上可見，這種算法也是把所有的可能路徑都列出來，再從中找出旅費最少的那條，顯而易見也是一種很費時的算法。那條，顯而易見也是一種很費時的算法。 最短路徑問題的求解最短路徑問題的求解 二、二、 啟發(fā)式搜索啟發(fā)式搜索在寬度優(yōu)先搜索算法的基礎上，每次并不是把所有可展開的結點展開，在寬度優(yōu)先搜索算法的基礎上，每次并

9、不是把所有可展開的結點展開，而是對所有沒有展開的結點，利用一個自己確定的估價函數對所有沒展開而是對所有沒有展開的結點，利用一個自己確定的估價函數對所有沒展開的結點進行估價，從而找出最應該被展開的結點（也就是說我們要找的答的結點進行估價，從而找出最應該被展開的結點（也就是說我們要找的答案最有可能是從該結點展開），而把該結點展開，直到找到目標結點為止。案最有可能是從該結點展開），而把該結點展開，直到找到目標結點為止。這種算法最關鍵的問題就是如何確定估價函數，估價函數越準，則能這種算法最關鍵的問題就是如何確定估價函數，估價函數越準，則能越快找到答案。這種算法實現起來并不難，只不過難在找準估價函數，大

10、越快找到答案。這種算法實現起來并不難，只不過難在找準估價函數，大家可以自已找相關資料學習和思考。家可以自已找相關資料學習和思考。 最短路徑問題的求解最短路徑問題的求解 三、等代價搜索法三、等代價搜索法等代價搜索法也是在寬度優(yōu)先搜索的基礎上進行了部分優(yōu)化的一種算法，它與等代價搜索法也是在寬度優(yōu)先搜索的基礎上進行了部分優(yōu)化的一種算法，它與啟發(fā)式搜索的相似之處都是每次只展開某一個結點（不是展開所有結點），不同之啟發(fā)式搜索的相似之處都是每次只展開某一個結點（不是展開所有結點），不同之處在于：它不需要去另找專門的估價函數，而是以該結點到處在于：它不需要去另找專門的估價函數，而是以該結點到A A點的距離作

11、為估價值，點的距離作為估價值，也就是說，等代價搜索法是啟發(fā)式搜索的一種簡化版本。它的大體思路是：也就是說，等代價搜索法是啟發(fā)式搜索的一種簡化版本。它的大體思路是：1 1、 從從A A點開始依次展開得到點開始依次展開得到ABAB（7 7）、）、ACAC（3 3）、）、ADAD（1010）、）、AEAE（1515）四個新）四個新結點，把第一層結點結點，把第一層結點A A標記為已展開，并且每個新結點要記錄下其旅費（括號中的標記為已展開，并且每個新結點要記錄下其旅費（括號中的數字）；數字）；2 2、 把未展開過的把未展開過的ABAB、ACAC、ADAD、AEAE四個結點中距離最小的一個展開，即展開四個

12、結點中距離最小的一個展開，即展開ACAC（3 3）結點，得到）結點，得到ACBACB（8 8）、）、ACDACD（1616）、）、ACEACE（1313）三個結點，并把結點）三個結點，并把結點ACAC標記為標記為已展開；已展開；3 3、 再從未展開的所有結點中找出距離最小的一個展開，即展開再從未展開的所有結點中找出距離最小的一個展開，即展開ABAB（7 7）結點，）結點，得到得到ABCABC（1212）、）、ABDABD（2020）、）、ABEABE（1919）三個結點，并把結點）三個結點，并把結點ABAB標記為已展開；標記為已展開；4 4、 再次從未展開的所有結點中找出距離最小的一個展開，即

13、展開再次從未展開的所有結點中找出距離最小的一個展開，即展開ACBACB（8 8）結）結點，點，；5 5、 每次展開所有未展開的結點中距離最小的那個結點，直到展開的新結點中每次展開所有未展開的結點中距離最小的那個結點，直到展開的新結點中出現目標情況（結點含有出現目標情況（結點含有5 5個字母）時，即得到了結果。個字母）時，即得到了結果。 最短路徑問題的求解最短路徑問題的求解 小結：小結： 由上可見，啟發(fā)式搜索和等代價搜索法并沒有象寬度優(yōu)先搜索由上可見，啟發(fā)式搜索和等代價搜索法并沒有象寬度優(yōu)先搜索一樣展開所有結點，只是根據某一原則（或某一估價函數值）每次一樣展開所有結點，只是根據某一原則（或某一估

14、價函數值）每次展開距離展開距離A A點最近的那個結點（或是估價函數計算出的最可能的那點最近的那個結點（或是估價函數計算出的最可能的那個結點），反復下去即可最終得到答案。雖然中途有時也展開了一個結點），反復下去即可最終得到答案。雖然中途有時也展開了一些并不是答案的結點，但這種展開并不是大規(guī)模的，不是全部展開，些并不是答案的結點，但這種展開并不是大規(guī)模的，不是全部展開，因而耗時要比寬度優(yōu)先搜索小得多。因而耗時要比寬度優(yōu)先搜索小得多。最短路徑問題的求解最短路徑問題的求解 例例2 2、題目基本同例、題目基本同例1 1，現在把權定義成距離，現在，現在把權定義成距離，現在要求要求A A點到點到E E點的最

15、短路徑，但并不要求每個城市都點的最短路徑，但并不要求每個城市都要走一遍。要走一遍。 例例1 1、假設、假設A A、B B、C C、D D、E E各個城市之間旅費如下圖紅各個城市之間旅費如下圖紅色數字所示。某人想從城市色數字所示。某人想從城市A A出發(fā)游覽各城市一遍，出發(fā)游覽各城市一遍，而所用旅費最少，試編程輸出結果。而所用旅費最少，試編程輸出結果。 問題分析問題分析 既然不要求每個點都要走一遍，只要距離最短即可，那么普通的寬度優(yōu)先搜索已經沒有什么意義了，既然不要求每個點都要走一遍，只要距離最短即可，那么普通的寬度優(yōu)先搜索已經沒有什么意義了，實際上就是窮舉。那么等代價搜索能不能再用在這題上呢？答

16、案是肯定的，但到底搜索到什么時候才能得實際上就是窮舉。那么等代價搜索能不能再用在這題上呢？答案是肯定的，但到底搜索到什么時候才能得到答案呢？這可是個很荊手的問題。到答案呢？這可是個很荊手的問題。是不是搜索到一個結點是以是不是搜索到一個結點是以E E結束時就停止呢？顯然不對。結束時就停止呢？顯然不對。那么是不是要把所有以那么是不是要把所有以E E為結束的結點全部搜索出來呢？這簡直就是寬度優(yōu)先搜索了，顯然不對。為結束的結點全部搜索出來呢？這簡直就是寬度優(yōu)先搜索了，顯然不對。實際上，實際上，應該是搜索到：當我們確定將要展開的某個結點（即所有未展開的結點中距離最小的那個點）應該是搜索到：當我們確定將要

17、展開的某個結點（即所有未展開的結點中距離最小的那個點）的最后一個字母是的最后一個字母是E E時，這個結點就是我們所要求的答案！因為比這個結點大的點再展開得到的解顯然不時，這個結點就是我們所要求的答案！因為比這個結點大的點再展開得到的解顯然不可能比這個結點優(yōu)！可能比這個結點優(yōu)！ 那么，除了等代價搜索外，有沒有其它辦法了呢？下面就介紹這種求最短路徑問題的其它幾種成熟算那么，除了等代價搜索外，有沒有其它辦法了呢？下面就介紹這種求最短路徑問題的其它幾種成熟算法。法。 最短路徑問題的求解最短路徑問題的求解 四、寬度優(yōu)先搜索四、寬度優(yōu)先搜索+ +剪枝剪枝 搜索之所以低效，是因為在搜索過程中存在著大量的重復

18、和不必要的搜索。因此，提高搜索效率的關搜索之所以低效，是因為在搜索過程中存在著大量的重復和不必要的搜索。因此，提高搜索效率的關鍵在于減少無意義的搜索。鍵在于減少無意義的搜索。假如在搜索時已經搜出從起點假如在搜索時已經搜出從起點A A到點到點B B的某一條路徑的長度是的某一條路徑的長度是X X，那么我們就可以，那么我們就可以知道，從知道，從A A到到B B的最短路徑長度必定的最短路徑長度必定XX，因此，其他從，因此，其他從A A到到B B的長度大于或等于的長度大于或等于X X的路徑可以一律剔除。的路徑可以一律剔除。具體具體實現時，可以開一個數組實現時，可以開一個數組h1.nh1.n，n n是結點

19、總數，是結點總數，hihi表示從起點到結點表示從起點到結點i i的最短路徑長度。的最短路徑長度。 算法流程如下：算法流程如下：1 1、初始化：初始化： 將起點將起點startstart入隊，入隊，hstart:=0hstart:=0，hk:=maxlongint(1=k=nhk:=maxlongint(1=k=n，且，且kstart)kstart)。2 2、repeatrepeat 取出隊頭結點賦給取出隊頭結點賦給t t； while twhile t有相鄰的結點沒被擴展有相鄰的結點沒被擴展 beginbegin t t擴展出新的結點擴展出新的結點newpnewp； 如果如果 ht+wt,ne

20、wp hnewpht+wt,newp hnewp， 則將則將newpnewp入隊，把入隊，把hnewphnewp的值更新為的值更新為ht+wt,newpht+wt,newp； EndEnd until until 隊列空；隊列空； 最短路徑問題的求解最短路徑問題的求解 五、迭代法五、迭代法 該算法的中心思想是：任意兩點該算法的中心思想是：任意兩點i,ji,j間的最短距離（記為間的最短距離（記為DijDij）會等于從）會等于從i i點出發(fā)到達點出發(fā)到達j j點的以任一點為點的以任一點為中轉點的所有可能的方案中，距離最短的一個。即：中轉點的所有可能的方案中，距離最短的一個。即：Dij = min

21、Dij , Dik+Dkj Dij = min Dij , Dik+Dkj ，1=k=n1=k=n。這樣，我們就找到了一個類似動態(tài)規(guī)劃的表達式，只不過這里我們不把它當作動態(tài)規(guī)劃去處理，而是這樣，我們就找到了一個類似動態(tài)規(guī)劃的表達式，只不過這里我們不把它當作動態(tài)規(guī)劃去處理，而是做一個二維數組用以存放任意兩點間的最短距離，利用上述公式不斷地對數組中的數據進行處理，直到各做一個二維數組用以存放任意兩點間的最短距離，利用上述公式不斷地對數組中的數據進行處理，直到各數據不再變化為止，這時即可得到數據不再變化為止，這時即可得到A A到到E E的最短路徑。的最短路徑。算法流程如下：算法流程如下： DiDi表

22、示從起點到表示從起點到i i的最短路的長度，的最短路的長度，g g是鄰接矩陣，是鄰接矩陣，s s表示起點；表示起點； 1 1、Di:=gs,i (1=i=n)Di:=gs,i (1=iDk+gk,j then if DjDk+gk,j then begin Dj:= Dk+gk,j; c:=true; end; begin Dj:= Dk+gk,j; c:=true; end; Until not c Until not c； 這種算法是產生這樣一個過程：不斷地求一個數字最短距離矩陣中的數據的值，而當所有這種算法是產生這樣一個過程：不斷地求一個數字最短距離矩陣中的數據的值，而當所有數據都已經不

23、能再變化時，就已經達到了目標的平衡狀態(tài)，這時最短距離矩陣中的值就是對應數據都已經不能再變化時，就已經達到了目標的平衡狀態(tài)，這時最短距離矩陣中的值就是對應的兩點間的最短距離。的兩點間的最短距離。 最短路徑問題的求解最短路徑問題的求解 六、動態(tài)規(guī)劃六、動態(tài)規(guī)劃 動態(tài)規(guī)劃算法已經成為了許多難題的首選算法。某些最短路徑問題也可以用動態(tài)規(guī)劃來解決，通動態(tài)規(guī)劃算法已經成為了許多難題的首選算法。某些最短路徑問題也可以用動態(tài)規(guī)劃來解決，通常這類最短路徑問題所對應的圖必須是有向無回路圖。因為如果存在回路，動態(tài)規(guī)劃的無后效性就無常這類最短路徑問題所對應的圖必須是有向無回路圖。因為如果存在回路，動態(tài)規(guī)劃的無后效性就

24、無法滿足。法滿足。我們知道，動態(tài)規(guī)劃算法與遞歸算法的不同之處在于它們的算法表達式：我們知道，動態(tài)規(guī)劃算法與遞歸算法的不同之處在于它們的算法表達式： 遞歸：類似遞歸：類似f(n)=x1f(n)=x1* *f(n-1)+x2f(n-1)+x2* *f(n-2)f(n-2)，即可以找到一個確定的關系的表達式；，即可以找到一個確定的關系的表達式；動態(tài)規(guī)劃：類似動態(tài)規(guī)劃：類似f(n)=min(f(n-1)+x1,f(n-2)+x2)f(n)=min(f(n-1)+x1,f(n-2)+x2)，即我們無法找到確定關系的表達式，只能，即我們無法找到確定關系的表達式，只能找到這樣一個不確定關系的表達式，找到這樣

25、一個不確定關系的表達式，f(n)f(n)的值是動態(tài)的，隨著的值是動態(tài)的，隨著f(n-1),f(n-2)f(n-1),f(n-2)等值的改變而確定跟誰相等值的改變而確定跟誰相關。關。為了給問題劃分階段，必須對圖進行一次拓撲排序，然后按照拓撲排序的結果來動態(tài)規(guī)劃。為了給問題劃分階段，必須對圖進行一次拓撲排序，然后按照拓撲排序的結果來動態(tài)規(guī)劃。 譬如，有如下兩個有向圖：譬如，有如下兩個有向圖： 3BD C E A9852143BD C E A985214最短路徑問題的求解最短路徑問題的求解 右圖因為存在回路而不能用動態(tài)規(guī)劃。而左圖是無回路的，所以可以用動態(tài)規(guī)劃解決。右圖因為存在回路而不能用動態(tài)規(guī)劃。

26、而左圖是無回路的，所以可以用動態(tài)規(guī)劃解決。對左圖拓撲排序，得到的序列是對左圖拓撲排序，得到的序列是A A、B B、D D、C C、E E。設設F(E)F(E)表示從表示從A A到到E E的最短路徑長度，然后按照拓撲序列的先后順序進行動態(tài)規(guī)劃：的最短路徑長度，然后按照拓撲序列的先后順序進行動態(tài)規(guī)劃： F(A)=0F(A)=0 F(B)=min F(A) +3=3 F(B)=min F(A) +3=3 F(D)=min F(A)+8, F(B)+2 =5 F(D)=min F(A)+8, F(B)+2 =5 F(C)=min F(B)+9, F(D)+5 =10 F(C)=min F(B)+9,

27、F(D)+5 =10 F(E)=min F(D)+1, F(C)+4 =6 F(E)=min F(D)+1, F(C)+4 =6總的式子是：總的式子是：F(i)=min F(k)+dis(i,k) F(i)=min F(k)+dis(i,k) ，k k與與i i必須相連，且在拓撲序列中，必須相連，且在拓撲序列中，k k在在i i之前。之前。3BD C E A9852143BD C E A985214最短路徑問題的求解最短路徑問題的求解 七、標號法七、標號法標號法是一種非常直觀的求最短路徑的算法，單從分析過程來看，我們可以用一個數軸簡單地表標號法是一種非常直觀的求最短路徑的算法，單從分析過程來看

28、，我們可以用一個數軸簡單地表示這種算法：示這種算法：1 1、 以以A A點為點為0 0點，展開與其相鄰的點，并在數軸中標出。點，展開與其相鄰的點，并在數軸中標出。 2 2、因為、因為C C點離起點點離起點A A最近，因此可以斷定最近，因此可以斷定C C點一定是由點一定是由A A直接到直接到C C點這條路徑是最短的（因為點這條路徑是最短的（因為A A、C C兩點兩點間沒有其它的點，所以間沒有其它的點，所以C C點可以確定是由點可以確定是由A A點直接到達為最短路徑）。因而就可以以已經確定的點直接到達為最短路徑）。因而就可以以已經確定的C C點點為當前展開點，展開與為當前展開點，展開與C C點想連

29、的所有點點想連的所有點AA、BB、DD、EE。 3 3、由數軸可見，、由數軸可見，A A與與AA點相比，點相比，A A點離原點近，因而保留點離原點近，因而保留A A點，刪除點，刪除AA點，相應的，點，相應的，B B、BB點保留點保留B B點，點，D D、DD保留保留DD，E E、EE保留保留EE，得到下圖：，得到下圖： 最短路徑問題的求解最短路徑問題的求解 4 4、此時再以離原點最近的未展開的點、此時再以離原點最近的未展開的點B B聯(lián)接的所有點，處理后，再展開離原點最近未展開的聯(lián)接的所有點，處理后，再展開離原點最近未展開的D D點，點，處理后得到如下圖的最終結果：處理后得到如下圖的最終結果：

30、5 5、由上圖可以得出結論：點、由上圖可以得出結論：點C C、B B、D D、E E就是點就是點A A到它們的最短路徑（注意：這些路徑并不是經過了到它們的最短路徑（注意：這些路徑并不是經過了所有點，而是只經過了其中的若干個點，而且到每一個點的那條路徑不一定相同）。因而所有點，而是只經過了其中的若干個點，而且到每一個點的那條路徑不一定相同）。因而A A到到E E的最的最短距離就是短距離就是1313。至于它經過了哪幾個點大家可在上述過程中加以記錄即可。至于它經過了哪幾個點大家可在上述過程中加以記錄即可。 最短路徑問題的求解最短路徑問題的求解 八、八、DijkstraDijkstra算法（從一個頂點

31、到其余各頂點的最短路徑，單源最短路徑）算法（從一個頂點到其余各頂點的最短路徑，單源最短路徑） 例例3 3、如下圖，假設、如下圖，假設C C1 1,C,C2 2,C,C3 3,C,C4 4,C,C5 5,C,C6 6是六座城市，他們之間的連線表示兩是六座城市，他們之間的連線表示兩城市間有道路相通，連線旁的數字表示路程。請編寫一程序，找出城市間有道路相通，連線旁的數字表示路程。請編寫一程序，找出C C1 1到到C Ci i的最短路徑的最短路徑(2i6)(2i6)，輸出路徑序列及最短路徑的路程長度。，輸出路徑序列及最短路徑的路程長度。 最短路徑問題的求解最短路徑問題的求解 問題分析問題分析 對于一個

32、含有對于一個含有n n個頂點和個頂點和e e條邊的圖來說，從某一個頂點條邊的圖來說，從某一個頂點ViVi到其余任一頂點到其余任一頂點VjVj的最短路徑，可的最短路徑，可能是它們之間的邊（能是它們之間的邊（ViVi，VjVj），也可能是經過），也可能是經過k k個中間頂點和個中間頂點和k+1k+1條邊所形成的路徑條邊所形成的路徑(1kn-2)(1kn-2)。下面給出解決這個問題的下面給出解決這個問題的DijkstraDijkstra算法思想。算法思想。 設圖設圖G G用鄰接矩陣的方式存儲在用鄰接矩陣的方式存儲在GAGA中，中，GAi,j=maxintGAi,j=maxint表示表示ViVi，Vj

33、Vj是不關聯(lián)的，否則為權值是不關聯(lián)的，否則為權值（大于（大于0 0的實數）。設集合的實數）。設集合S S用來保存已求得最短路徑的終點序號，初始時用來保存已求得最短路徑的終點序號，初始時S=ViS=Vi表示只有源點，表示只有源點，以后每求出一個終點以后每求出一個終點VjVj，就把它加入到集合中并作為新考慮的中間頂點。設數組，就把它加入到集合中并作為新考慮的中間頂點。設數組dist1.ndist1.n用來用來存儲當前求得的最短路徑，初始時存儲當前求得的最短路徑，初始時ViVi，VjVj如果是關聯(lián)的，則如果是關聯(lián)的，則distjdistj等于權值，否則等于等于權值，否則等于maxintmaxint，

34、以后隨著新考慮的中間頂點越來越多，以后隨著新考慮的中間頂點越來越多，distjdistj可能越來越小。再設一個與可能越來越小。再設一個與distdist對應的數組對應的數組path1.npath1.n用來存放當前最短路徑的邊，初始時為用來存放當前最短路徑的邊，初始時為ViVi到到VjVj的邊，如果不存在邊則為空。的邊，如果不存在邊則為空。 執(zhí)行時，先從執(zhí)行時，先從S S以外的頂點（即待求出最短路徑的終點）所對應的以外的頂點（即待求出最短路徑的終點）所對應的distdist數組元素中，找出其數組元素中，找出其值最小的元素（假設為值最小的元素（假設為distmdistm），該元素值就是從源點），該

35、元素值就是從源點ViVi到終點到終點VmVm的最短路徑長度，對應的的最短路徑長度，對應的pathmpathm中的頂點或邊的序列即為最短路徑。接著把中的頂點或邊的序列即為最短路徑。接著把VmVm并入集合并入集合S S中，然后以中，然后以VmVm作為新考慮的中作為新考慮的中間頂點，對間頂點，對S S以外的每個頂點以外的每個頂點VjVj，比較，比較distm+GAm,jdistm+GAm,j的的distjdistj的大小，若前者小，表明加入的大小，若前者小，表明加入了新的中間頂點后可以得到更好的方案，即可求得更短的路徑，則用它代替了新的中間頂點后可以得到更好的方案，即可求得更短的路徑，則用它代替di

36、stjdistj，同時把，同時把VjVj或邊（或邊（VmVm，VjVj）并入到）并入到pathjpathj中。重復以上過程中。重復以上過程n-2n-2次，即可在次，即可在distdist數組中得到從源點到其余數組中得到從源點到其余各終點的最段路徑長度，對應的各終點的最段路徑長度，對應的pathpath數組中保存著相應的最段路徑。數組中保存著相應的最段路徑。 對于上圖，采用對于上圖，采用DijkstraDijkstra算法找出算法找出C C1 1到到C Ci i之間的最短路徑之間的最短路徑(2i6)(2i6)的過程如下：的過程如下： 最短路徑問題的求解最短路徑問題的求解 123456Dist04

37、8maxintmaxintmaxintPathC1C1,C2C1,C3初始時：初始時： 第一次：選擇第一次：選擇m=2m=2，則，則S=CS=C1 1,C,C2 2 ，計算比較，計算比較dist2+GA2,jdist2+GA2,j與與distjdistj的大小的大小 123456Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：選擇第二次：選擇m=3m=3，則，則S=CS=C1 1,C,C2 2,C,C3 3 ，計算比較，計算比較dist3+GA3,jdist3+GA3,j與與distjdistj的大小的大小 123456Dist04

38、789maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5第三次：選擇第三次：選擇m=4m=4，S=CS=C1 1,C,C2 2,C,C3 3,C,C4 4 ，計算比較，計算比較dist4+GA4,jdist4+GA4,j與與distjdistj的大小的大小 123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6最短路徑問題的求解最短路徑問題的求解 第四次：選擇第四次：選擇m=5m=5，則，則S=CS=C1 1,C,C2 2,C,C3 3,C,C4 4,C,C5 5 ，計算比較，計

39、算比較dist5+GA5,jdist5+GA5,j與與distjdistj的大小的大小 123456Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因為該圖的度因為該圖的度n=6n=6，所以執(zhí)行，所以執(zhí)行n-2=4n-2=4次后結束，此時通過次后結束，此時通過distdist和和pathpath數組可以看出：數組可以看出：C C1 1到到C C2 2的最短路徑為：的最短路徑為：C C1 1CC2 2，長度為：，長度為：4 4；C C1 1到到C C3 3的最短路徑為：的最短路徑為：C C1 1CC2 2CC3 3，長

40、度為：，長度為：7 7；C C1 1到到C C4 4的最短路徑為：的最短路徑為：C C1 1CC2 2CC4 4，長度為：，長度為：8 8；C C1 1到到C C5 5的最短路徑為：的最短路徑為：C C1 1CC2 2CC3 3CC5 5，長度為：，長度為：9 9；C C1 1到到C C6 6的最短路徑為：的最短路徑為：C C1 1CC2 2CC3 3CC5 5CC6 6，長度為：，長度為：1313；123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6最短路徑問題的求解最短路徑問題的求解 下面給出具體的下面給出具體

41、的DijkstraDijkstra算法框架（注：為了實現上的方便，我們用一個一維數組算法框架（注：為了實現上的方便，我們用一個一維數組s1.ns1.n代替集合代替集合S S，用來保存已求得最短路徑的終點集合，即如果，用來保存已求得最短路徑的終點集合，即如果sj=0sj=0表示頂點表示頂點VjVj不在集合中，反之，不在集合中，反之，sj=1sj=1表示頂點表示頂點VjVj已在集合中）。已在集合中）。 Procedure Dijkstra(GA,dist,path,i)Procedure Dijkstra(GA,dist,path,i)； 表示求表示求ViVi到圖到圖G G中其余頂點的最短路徑，中

42、其余頂點的最短路徑，GAGA為圖為圖G G的鄰接矩陣，的鄰接矩陣，distdist和和pathpath為變量型參數，為變量型參數， 其中其中pathpath的基類型為集合的基類型為集合 Begin Begin For j:=1 To n Do Begin For j:=1 To n Do Begin 初始化初始化 If ji Then sj:=0 Else sj:=1 If ji Then sj:=0 Else sj:=1； distj:=GAi,jdistj:=GAi,j； If distjmaxint Then pathj:=i+j Else pathj:= If distjmaxint

43、Then pathj:=i+j Else pathj:= ； EndEnd；最短路徑問題的求解最短路徑問題的求解 For k:=1 To n-2 DoFor k:=1 To n-2 Do Begin Begin w:=maxint w:=maxint；m:=im:=i； For j:=1 To n Do For j:=1 To n Do 求出第求出第k k個終點個終點VmVm If (sj=0) and (distjw) Then Begin m:=j If (sj=0) and (distjw) Then Begin m:=j；w:=distjw:=distj； EndEnd； If mi

44、Then sm:=1 else exitIf mi Then sm:=1 else exit； 若條件成立，則把若條件成立，則把VmVm加入到加入到S S中，中， 否則退出循環(huán)，因為剩余的終點，其最短路徑長度均為否則退出循環(huán)，因為剩余的終點，其最短路徑長度均為maxintmaxint，無需再計算下去，無需再計算下去 For j:=1 To n Do For j:=1 To n Do 對對sj=0sj=0的更優(yōu)元素作必要修改的更優(yōu)元素作必要修改 If (sj=0) and (distm+GAm,jdistj) If (sj=0) and (distm+GAm,jdistj) Then Begin

45、 Distj:=distm+GAm,j Then Begin Distj:=distm+GAm,j；pathj:=pathm+jpathj:=pathm+j；EndEnd； EndEnd；EndEnd；最短路徑問題的求解最短路徑問題的求解 九、九、FloydFloyd算法算法例例4 4、求任意一對頂點之間的最短路徑。、求任意一對頂點之間的最短路徑。 問題分析問題分析 這個問題的解法有兩種：一是分別以圖中的每個頂點為源點共這個問題的解法有兩種：一是分別以圖中的每個頂點為源點共調用調用n n次次DijkstraDijkstra算法算法，這種算法的時間復雜度為，這種算法的時間復雜度為O O（n n3

46、 3）；另外還有一種算法：）；另外還有一種算法：FloydFloyd算法算法，它的思路，它的思路簡單，但時間復雜度仍然為簡單，但時間復雜度仍然為O O（n n3 3），下面介紹），下面介紹FloydFloyd算法。算法。 設具有設具有n n個頂點的一個帶權圖個頂點的一個帶權圖G G的鄰接矩陣用的鄰接矩陣用GAGA表示，再設一個與表示，再設一個與GAGA同類型的表同類型的表示每對頂點之間最短路徑長度的二維數組示每對頂點之間最短路徑長度的二維數組A A，A A的初值等于的初值等于GAGA。FloydFloyd算法需要在算法需要在A A上上進行進行n n次運算，每次以次運算，每次以V Vk k（1k

47、n1kn）作為新考慮的中間點，求出每對頂點之間的當前）作為新考慮的中間點，求出每對頂點之間的當前最短路徑長度，最后依次運算后，最短路徑長度，最后依次運算后，A A中的每個元素中的每個元素AiAi，jj就是圖就是圖G G中從頂點中從頂點V Vi i到頂點到頂點V Vj j的最短路徑長度。再設一個二維數組的最短路徑長度。再設一個二維數組P1.n,1.nP1.n,1.n，記錄最短路徑，其元素類型為，記錄最短路徑，其元素類型為集合類型集合類型set of 1.nset of 1.n。 FloydFloyd算法的具體描述如下：算法的具體描述如下： 最短路徑問題的求解最短路徑問題的求解 Procedure

48、 Floyd(GAProcedure Floyd(GA，A A，P)P)； BeginBegin For i:=1 To n Do For i:=1 To n Do 最短路徑長度數組和最短路徑數組初始化最短路徑長度數組和最短路徑數組初始化 For j:=1 To n Do For j:=1 To n Do Begin Begin Ai,j:=GAi,j Ai,j:=GAi,j； If Ai,jmaxint Then pi,j:=i+jIf Ai,jmaxint Then pi,j:=i+jElse pi,j:= Else pi,j:= ； EndEnd； For k:=1 To n Do nF

49、or k:=1 To n Do n次運算次運算 For i:=1 To n Do For i:=1 To n Do For j:=1 To n Do For j:=1 To n Do Begin Begin If (i=k)or(j=k)or(i=j) Then Continue If (i=k)or(j=k)or(i=j) Then Continue； 無需計算，直接進入下一輪循環(huán)無需計算，直接進入下一輪循環(huán) If Ai,k+Ak,jAi,j Then Begin If Ai,k+Ak,jAi,j Then Begin 找到更短路徑、保存找到更短路徑、保存 Ai,j Ai,j：= Ai,k+

50、Ak,j= Ai,k+Ak,j； Pi,jPi,j：= Pi,k+Pk,j= Pi,k+Pk,j； EndEnd； EndEnd； EndEnd；最短路徑問題的求解最短路徑問題的求解 總結與思考：總結與思考： 最短路徑問題的求解還不止這幾種算法，比如還有分枝定界等等，而最短路徑問題的求解還不止這幾種算法，比如還有分枝定界等等，而且大家也可以創(chuàng)造出各種各樣的新算法來。不同的最短路徑問題到底用哪且大家也可以創(chuàng)造出各種各樣的新算法來。不同的最短路徑問題到底用哪種算法，以及還需要對該種算法作什么改動，是非常重要的，這種能力往種算法，以及還需要對該種算法作什么改動，是非常重要的，這種能力往往是很多同學所

51、欠缺的，這需要大家在平常的訓練中多做這類題目，還要往是很多同學所欠缺的，這需要大家在平常的訓練中多做這類題目，還要多總結，以達到熟能生巧的境界。多總結，以達到熟能生巧的境界。 在學習完最短路徑后，有沒有人想到：能不能修改這些算法，實現求在學習完最短路徑后，有沒有人想到：能不能修改這些算法，實現求最長路徑的問題呢？最長路徑的問題呢？ 這種發(fā)散性的思維是值得稱贊的，對于不存在回路的有向圖，這種算這種發(fā)散性的思維是值得稱贊的，對于不存在回路的有向圖，這種算法是可行的。但需要提醒的是：如果有向圖出現了回路，按照最長路徑的法是可行的。但需要提醒的是：如果有向圖出現了回路，按照最長路徑的思想和判斷要求，則計算可能沿著回路無限制的循環(huán)下去。思想和判斷要求，