最短路徑問(wèn)題的求解

1、最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 最短路徑是圖論中的一個(gè)重要問(wèn)題，具有很高的實(shí)用價(jià)值，也是信息最短路徑是圖論中的一個(gè)重要問(wèn)題，具有很高的實(shí)用價(jià)值，也是信息學(xué)競(jìng)賽中常見的一類中等難度的題目，這類問(wèn)題很能聯(lián)系實(shí)際，考察學(xué)生學(xué)競(jìng)賽中常見的一類中等難度的題目，這類問(wèn)題很能聯(lián)系實(shí)際，考察學(xué)生的建模能力，反映出學(xué)生的創(chuàng)造性思維，因?yàn)橛行┛此聘疃搪窂胶翢o(wú)關(guān)的建模能力，反映出學(xué)生的創(chuàng)造性思維，因?yàn)橛行┛此聘疃搪窂胶翢o(wú)關(guān)系的問(wèn)題，也可以歸結(jié)為最短路徑問(wèn)題來(lái)求解。系的問(wèn)題，也可以歸結(jié)為最短路徑問(wèn)題來(lái)求解。 在帶權(quán)圖在帶權(quán)圖G=G=（V V，E E）中，若頂點(diǎn)）中，若頂點(diǎn) Vi,VjVi,Vj是圖是圖G G

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

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

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

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

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

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

8、BAEDCB，每個(gè)結(jié)點(diǎn)也需記錄下其旅費(fèi)；，每個(gè)結(jié)點(diǎn)也需記錄下其旅費(fèi)；5 5、 到此，所有可能的結(jié)點(diǎn)均已展開，而第五層結(jié)點(diǎn)中旅費(fèi)最少的那個(gè)就是題到此，所有可能的結(jié)點(diǎn)均已展開，而第五層結(jié)點(diǎn)中旅費(fèi)最少的那個(gè)就是題目的解了。目的解了。由上可見，這種算法也是把所有的可能路徑都列出來(lái)，再?gòu)闹姓页雎觅M(fèi)最少的由上可見，這種算法也是把所有的可能路徑都列出來(lái)，再?gòu)闹姓页雎觅M(fèi)最少的那條，顯而易見也是一種很費(fèi)時(shí)的算法。那條，顯而易見也是一種很費(fèi)時(shí)的算法。 最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 二、二、 啟發(fā)式搜索啟發(fā)式搜索在寬度優(yōu)先搜索算法的基礎(chǔ)上，每次并不是把所有可展開的結(jié)點(diǎn)展開，在寬度優(yōu)先搜索算法的基礎(chǔ)上，每次并

9、不是把所有可展開的結(jié)點(diǎn)展開，而是對(duì)所有沒(méi)有展開的結(jié)點(diǎn)，利用一個(gè)自己確定的估價(jià)函數(shù)對(duì)所有沒(méi)展開而是對(duì)所有沒(méi)有展開的結(jié)點(diǎn)，利用一個(gè)自己確定的估價(jià)函數(shù)對(duì)所有沒(méi)展開的結(jié)點(diǎn)進(jìn)行估價(jià)，從而找出最應(yīng)該被展開的結(jié)點(diǎn)（也就是說(shuō)我們要找的答的結(jié)點(diǎn)進(jìn)行估價(jià)，從而找出最應(yīng)該被展開的結(jié)點(diǎn)（也就是說(shuō)我們要找的答案最有可能是從該結(jié)點(diǎn)展開），而把該結(jié)點(diǎn)展開，直到找到目標(biāo)結(jié)點(diǎn)為止。案最有可能是從該結(jié)點(diǎn)展開），而把該結(jié)點(diǎn)展開，直到找到目標(biāo)結(jié)點(diǎn)為止。這種算法最關(guān)鍵的問(wèn)題就是如何確定估價(jià)函數(shù)，估價(jià)函數(shù)越準(zhǔn)，則能這種算法最關(guān)鍵的問(wèn)題就是如何確定估價(jià)函數(shù)，估價(jià)函數(shù)越準(zhǔn)，則能越快找到答案。這種算法實(shí)現(xiàn)起來(lái)并不難，只不過(guò)難在找準(zhǔn)估價(jià)函數(shù)，大

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

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

12、結(jié)點(diǎn)中距離最小的一個(gè)展開，即展開ACAC（3 3）結(jié)點(diǎn)，得到）結(jié)點(diǎn)，得到ACBACB（8 8）、）、ACDACD（1616）、）、ACEACE（1313）三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)）三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)ACAC標(biāo)記為標(biāo)記為已展開；已展開；3 3、 再?gòu)奈凑归_的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開，即展開再?gòu)奈凑归_的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開，即展開ABAB（7 7）結(jié)點(diǎn)，）結(jié)點(diǎn)，得到得到ABCABC（1212）、）、ABDABD（2020）、）、ABEABE（1919）三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)）三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)ABAB標(biāo)記為已展開；標(biāo)記為已展開；4 4、 再次從未展開的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開，即

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

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

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

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

17、展開的某個(gè)結(jié)點(diǎn)（即所有未展開的結(jié)點(diǎn)中距離最小的那個(gè)點(diǎn)）的最后一個(gè)字母是的最后一個(gè)字母是E E時(shí)，這個(gè)結(jié)點(diǎn)就是我們所要求的答案！因?yàn)楸冗@個(gè)結(jié)點(diǎn)大的點(diǎn)再展開得到的解顯然不時(shí)，這個(gè)結(jié)點(diǎn)就是我們所要求的答案！因?yàn)楸冗@個(gè)結(jié)點(diǎn)大的點(diǎn)再展開得到的解顯然不可能比這個(gè)結(jié)點(diǎn)優(yōu)！可能比這個(gè)結(jié)點(diǎn)優(yōu)！ 那么，除了等代價(jià)搜索外，有沒(méi)有其它辦法了呢？下面就介紹這種求最短路徑問(wèn)題的其它幾種成熟算那么，除了等代價(jià)搜索外，有沒(méi)有其它辦法了呢？下面就介紹這種求最短路徑問(wèn)題的其它幾種成熟算法。法。 最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 四、寬度優(yōu)先搜索四、寬度優(yōu)先搜索+ +剪枝剪枝 搜索之所以低效，是因?yàn)樵谒阉鬟^(guò)程中存在著大量的重復(fù)

18、和不必要的搜索。因此，提高搜索效率的關(guān)搜索之所以低效，是因?yàn)樵谒阉鬟^(guò)程中存在著大量的重復(fù)和不必要的搜索。因此，提高搜索效率的關(guān)鍵在于減少無(wú)意義的搜索。鍵在于減少無(wú)意義的搜索。假如在搜索時(shí)已經(jīng)搜出從起點(diǎn)假如在搜索時(shí)已經(jīng)搜出從起點(diǎn)A A到點(diǎn)到點(diǎn)B B的某一條路徑的長(zhǎng)度是的某一條路徑的長(zhǎng)度是X X，那么我們就可以，那么我們就可以知道，從知道，從A A到到B B的最短路徑長(zhǎng)度必定的最短路徑長(zhǎng)度必定XX，因此，其他從，因此，其他從A A到到B B的長(zhǎng)度大于或等于的長(zhǎng)度大于或等于X X的路徑可以一律剔除。的路徑可以一律剔除。具體具體實(shí)現(xiàn)時(shí)，可以開一個(gè)數(shù)組實(shí)現(xiàn)時(shí)，可以開一個(gè)數(shù)組h1.nh1.n，n n是結(jié)點(diǎn)

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

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

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

22、示從起點(diǎn)到表示從起點(diǎn)到i i的最短路的長(zhǎng)度，的最短路的長(zhǎng)度，g g是鄰接矩陣，是鄰接矩陣，s s表示起點(diǎn)；表示起點(diǎn)； 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； 這種算法是產(chǎn)生這樣一個(gè)過(guò)程：不斷地求一個(gè)數(shù)字最短距離矩陣中的數(shù)據(jù)的值，而當(dāng)所有這種算法是產(chǎn)生這樣一個(gè)過(guò)程：不斷地求一個(gè)數(shù)字最短距離矩陣中的數(shù)據(jù)的值，而當(dāng)所有數(shù)據(jù)都已經(jīng)不

23、能再變化時(shí)，就已經(jīng)達(dá)到了目標(biāo)的平衡狀態(tài)，這時(shí)最短距離矩陣中的值就是對(duì)應(yīng)數(shù)據(jù)都已經(jīng)不能再變化時(shí)，就已經(jīng)達(dá)到了目標(biāo)的平衡狀態(tài)，這時(shí)最短距離矩陣中的值就是對(duì)應(yīng)的兩點(diǎn)間的最短距離。的兩點(diǎn)間的最短距離。 最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 六、動(dòng)態(tài)規(guī)劃六、動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃算法已經(jīng)成為了許多難題的首選算法。某些最短路徑問(wèn)題也可以用動(dòng)態(tài)規(guī)劃來(lái)解決，通動(dòng)態(tài)規(guī)劃算法已經(jīng)成為了許多難題的首選算法。某些最短路徑問(wèn)題也可以用動(dòng)態(tài)規(guī)劃來(lái)解決，通常這類最短路徑問(wèn)題所對(duì)應(yīng)的圖必須是有向無(wú)回路圖。因?yàn)槿绻嬖诨芈罚瑒?dòng)態(tài)規(guī)劃的無(wú)后效性就無(wú)常這類最短路徑問(wèn)題所對(duì)應(yīng)的圖必須是有向無(wú)回路圖。因?yàn)槿绻嬖诨芈?，?dòng)態(tài)規(guī)劃的無(wú)后效性就

24、無(wú)法滿足。法滿足。我們知道，動(dòng)態(tài)規(guī)劃算法與遞歸算法的不同之處在于它們的算法表達(dá)式：我們知道，動(dòng)態(tài)規(guī)劃算法與遞歸算法的不同之處在于它們的算法表達(dá)式： 遞歸：類似遞歸：類似f(n)=x1f(n)=x1* *f(n-1)+x2f(n-1)+x2* *f(n-2)f(n-2)，即可以找到一個(gè)確定的關(guān)系的表達(dá)式；，即可以找到一個(gè)確定的關(guān)系的表達(dá)式；動(dòng)態(tài)規(guī)劃：類似動(dòng)態(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)，即我們無(wú)法找到確定關(guān)系的表達(dá)式，只能，即我們無(wú)法找到確定關(guān)系的表達(dá)式，只能找到這樣一個(gè)不確定關(guān)系的表達(dá)式，找到這樣

25、一個(gè)不確定關(guān)系的表達(dá)式，f(n)f(n)的值是動(dòng)態(tài)的，隨著的值是動(dòng)態(tài)的，隨著f(n-1),f(n-2)f(n-1),f(n-2)等值的改變而確定跟誰(shuí)相等值的改變而確定跟誰(shuí)相關(guān)。關(guān)。為了給問(wèn)題劃分階段，必須對(duì)圖進(jìn)行一次拓?fù)渑判颍缓蟀凑胀負(fù)渑判虻慕Y(jié)果來(lái)動(dòng)態(tài)規(guī)劃。為了給問(wèn)題劃分階段，必須對(duì)圖進(jìn)行一次拓?fù)渑判颍缓蟀凑胀負(fù)渑判虻慕Y(jié)果來(lái)動(dòng)態(tài)規(guī)劃。 譬如，有如下兩個(gè)有向圖：譬如，有如下兩個(gè)有向圖： 3BD C E A9852143BD C E A985214最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 右圖因?yàn)榇嬖诨芈范荒苡脛?dòng)態(tài)規(guī)劃。而左圖是無(wú)回路的，所以可以用動(dòng)態(tài)規(guī)劃解決。右圖因?yàn)榇嬖诨芈范荒苡脛?dòng)態(tài)規(guī)劃。

26、而左圖是無(wú)回路的，所以可以用動(dòng)態(tài)規(guī)劃解決。對(duì)左圖拓?fù)渑判?，得到的序列是?duì)左圖拓?fù)渑判?，得到的序列是A A、B B、D D、C C、E E。設(shè)設(shè)F(E)F(E)表示從表示從A A到到E E的最短路徑長(zhǎng)度，然后按照拓?fù)湫蛄械南群箜樞蜻M(jìn)行動(dòng)態(tài)規(guī)劃：的最短路徑長(zhǎng)度，然后按照拓?fù)湫蛄械南群箜樞蜻M(jìn)行動(dòng)態(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必須相連，且在拓?fù)湫蛄兄校仨毾噙B，且在拓?fù)湫蛄兄?，k k在在i i之前。之前。3BD C E A9852143BD C E A985214最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 七、標(biāo)號(hào)法七、標(biāo)號(hào)法標(biāo)號(hào)法是一種非常直觀的求最短路徑的算法，單從分析過(guò)程來(lái)看，我們可以用一個(gè)數(shù)軸簡(jiǎn)單地表標(biāo)號(hào)法是一種非常直觀的求最短路徑的算法，單從分析過(guò)程來(lái)看

28、，我們可以用一個(gè)數(shù)軸簡(jiǎn)單地表示這種算法：示這種算法：1 1、 以以A A點(diǎn)為點(diǎn)為0 0點(diǎn)，展開與其相鄰的點(diǎn)，并在數(shù)軸中標(biāo)出。點(diǎn)，展開與其相鄰的點(diǎn)，并在數(shù)軸中標(biāo)出。 2 2、因?yàn)?、因?yàn)镃 C點(diǎn)離起點(diǎn)點(diǎn)離起點(diǎn)A A最近，因此可以斷定最近，因此可以斷定C C點(diǎn)一定是由點(diǎn)一定是由A A直接到直接到C C點(diǎn)這條路徑是最短的（因?yàn)辄c(diǎn)這條路徑是最短的（因?yàn)锳 A、C C兩點(diǎn)兩點(diǎn)間沒(méi)有其它的點(diǎn)，所以間沒(méi)有其它的點(diǎn)，所以C C點(diǎn)可以確定是由點(diǎn)可以確定是由A A點(diǎn)直接到達(dá)為最短路徑）。因而就可以以已經(jīng)確定的點(diǎn)直接到達(dá)為最短路徑）。因而就可以以已經(jīng)確定的C C點(diǎn)點(diǎn)為當(dāng)前展開點(diǎn)，展開與為當(dāng)前展開點(diǎn)，展開與C C點(diǎn)想連

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

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

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

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

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

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

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

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

37、8maxintmaxintmaxintPathC1C1,C2C1,C3初始時(shí)：初始時(shí)： 第一次：選擇第一次：選擇m=2m=2，則，則S=CS=C1 1,C,C2 2 ，計(jì)算比較，計(jì)算比較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 ，計(jì)算比較，計(jì)算比較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 ，計(jì)算比較，計(jì)算比較dist4+GA4,jdist4+GA4,j與與distjdistj的大小的大小 123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 第四次：選擇第四次：選擇m=5m=5，則，則S=CS=C1 1,C,C2 2,C,C3 3,C,C4 4,C,C5 5 ，計(jì)算比較，計(jì)

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

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

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

42、其余頂點(diǎn)的最短路徑，GAGA為圖為圖G G的鄰接矩陣，的鄰接矩陣，distdist和和pathpath為變量型參數(shù)，為變量型參數(shù)， 其中其中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；最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 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個(gè)終點(diǎn)個(gè)終點(diǎn)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)，因?yàn)槭Ｓ嗟慕K點(diǎn)，其最短路徑長(zhǎng)度均為否則退出循環(huán)，因?yàn)槭Ｓ嗟慕K點(diǎn)，其最短路徑長(zhǎng)度均為maxintmaxint，無(wú)需再計(jì)算下去，無(wú)需再計(jì)算下去 For j:=1 To n Do For j:=1 To n Do 對(duì)對(duì)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；最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 九、九、FloydFloyd算法算法例例4 4、求任意一對(duì)頂點(diǎn)之間的最短路徑。、求任意一對(duì)頂點(diǎn)之間的最短路徑。 問(wèn)題分析問(wèn)題分析 這個(gè)問(wèn)題的解法有兩種：一是分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共這個(gè)問(wèn)題的解法有兩種：一是分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共調(diào)用調(diào)用n n次次DijkstraDijkstra算法算法，這種算法的時(shí)間復(fù)雜度為，這種算法的時(shí)間復(fù)雜度為O O（n n3

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

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

48、 Floyd(GAProcedure Floyd(GA，A A，P)P)； BeginBegin For i:=1 To n Do For i:=1 To n Do 最短路徑長(zhǎng)度數(shù)組和最短路徑數(shù)組初始化最短路徑長(zhǎng)度數(shù)組和最短路徑數(shù)組初始化 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次運(yùn)算次運(yù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； 無(wú)需計(jì)算，直接進(jìn)入下一輪循環(huán)無(wú)需計(jì)算，直接進(jì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；最短路徑問(wèn)題的求解最短路徑問(wèn)題的求解 總結(jié)與思考：總結(jié)與思考： 最短路徑問(wèn)題的求解還不止這幾種算法，比如還有分枝定界等等，而最短路徑問(wèn)題的求解還不止這幾種算法，比如還有分枝定界等等，而且大家也可以創(chuàng)造出各種各樣的新算法來(lái)。不同的最短路徑問(wèn)題到底用哪且大家也可以創(chuàng)造出各種各樣的新算法來(lái)。不同的最短路徑問(wèn)題到底用哪種算法，以及還需要對(duì)該種算法作什么改動(dòng)，是非常重要的，這種能力往種算法，以及還需要對(duì)該種算法作什么改動(dòng)，是非常重要的，這種能力往往是很多同學(xué)所

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