1、最短路徑問題的求解,最短路徑是圖論中的一個重要問題，具有很高的實用價值，也是信息學(xué)競賽中常見的一類中等難度的題目，這類問題很能聯(lián)系實際，考察學(xué)生的建模能力，反映出學(xué)生的創(chuàng)造性思維，因為有些看似跟最短路徑毫無關(guān)系的問題，也可以歸結(jié)為最短路徑問題來求解。,在帶權(quán)圖G=（V，E）中，若頂點 Vi,Vj是圖G的兩個頂點，從頂點Vi到Vj的路徑長度定義為路徑上各條邊的權(quán)值之和。從頂點Vi到Vj可能有多條路徑，其中路徑長度最小的一條路徑稱為頂點Vi到Vj的最短路徑。,一般有兩類最短路徑問題：一類是求從某個頂點（源點）到其它頂點（終點）的最短路徑；另一類是求圖中每一對頂點間的最短路徑。,對于不帶權(quán)的圖，只要

2、人為的把每條邊加上權(quán)值1，即可當(dāng)作帶權(quán)圖一樣處理了。,最短路徑問題的求解,例1、假設(shè)A、B、C、D、E各個城市之間旅費如下圖紅色數(shù)字所示。某人想從城市A出發(fā)游覽各城市一遍，而所用旅費最少，試編程輸出結(jié)果。,問題分析 解這類問題時，很多同學(xué)往往不得要領(lǐng)，采用窮舉法把所有可能的情況全部列出，再找出其中旅費最少的那條路徑；或者采用遞歸（深搜）找出所有路徑，再找出旅費最少的那條。但這兩種方法都是費時非常多的解法，如果城市數(shù)目多的話則很可能要超時了。實際上我們知道，遞歸（深搜）之類的算法一般用于求所有解問題（例如求從A出發(fā)每個城市都要走一遍一共有哪幾種走法？），所以這些算法對于求最短路徑這類最優(yōu)解問題顯

3、然是不合適的。,首先，對于這類圖，我們都應(yīng)該先建立一個鄰接矩陣，存放任意兩點間的數(shù)據(jù)（如距離、費用、時間等），以便在程序中方便調(diào)用，以下介紹幾種常見的、更好的求最短路徑問題的算法。,最短路徑問題的求解,一、 寬度優(yōu)先搜索寬搜也并不是解決這類問題的優(yōu)秀算法，這里只是簡單介紹一下算法思路，為后面的優(yōu)秀算法做個鋪墊。具體如下：1、 從A點開始依次展開得到AB、AC、AD、AE四個新結(jié)點（第二層結(jié)點），當(dāng)然每個新結(jié)點要記錄下其旅費；2、 再次由AB展開得到ABC、ABD、ABE三個新結(jié)點（第三層結(jié)點），而由AC結(jié)點可展開得到ACB、ACD、ACE三個新結(jié)點，自然由AD可以展開得到ADB、ADC、ADE

4、，由AE可以展開得到AEB、AEC、AED等新結(jié)點，對于每個結(jié)點也須記錄下其旅費；3、 再把第三層結(jié)點全部展開，得到所有的第四層結(jié)點：ABCD、ABCE、ABDC、ABDE、ABEC、ABED、AEDB、AEDC，每個結(jié)點也需記錄下其旅費；4、 再把第四層結(jié)點全部展開，得到所有的第五層結(jié)點：ABCDE、ABCED、AEDBC、AEDCB，每個結(jié)點也需記錄下其旅費；5、 到此，所有可能的結(jié)點均已展開，而第五層結(jié)點中旅費最少的那個就是題目的解了。由上可見，這種算法也是把所有的可能路徑都列出來，再從中找出旅費最少的那條，顯而易見也是一種很費時的算法。,最短路徑問題的求解,二、 啟發(fā)式搜索在寬度優(yōu)先搜

5、索算法的基礎(chǔ)上，每次并不是把所有可展開的結(jié)點展開，而是對所有沒有展開的結(jié)點，利用一個自己確定的估價函數(shù)對所有沒展開的結(jié)點進行估價，從而找出最應(yīng)該被展開的結(jié)點（也就是說我們要找的答案最有可能是從該結(jié)點展開），而把該結(jié)點展開，直到找到目標(biāo)結(jié)點為止。這種算法最關(guān)鍵的問題就是如何確定估價函數(shù)，估價函數(shù)越準(zhǔn)，則能越快找到答案。這種算法實現(xiàn)起來并不難，只不過難在找準(zhǔn)估價函數(shù)，大家可以自已找相關(guān)資料學(xué)習(xí)和思考。,最短路徑問題的求解,三、等代價搜索法等代價搜索法也是在寬度優(yōu)先搜索的基礎(chǔ)上進行了部分優(yōu)化的一種算法，它與啟發(fā)式搜索的相似之處都是每次只展開某一個結(jié)點（不是展開所有結(jié)點），不同之處在于：它不需要去另找

6、專門的估價函數(shù)，而是以該結(jié)點到A點的距離作為估價值，也就是說，等代價搜索法是啟發(fā)式搜索的一種簡化版本。它的大體思路是：1、 從A點開始依次展開得到AB（7）、AC（3）、AD（10）、AE（15）四個新結(jié)點，把第一層結(jié)點A標(biāo)記為已展開，并且每個新結(jié)點要記錄下其旅費（括號中的數(shù)字）；2、 把未展開過的AB、AC、AD、AE四個結(jié)點中距離最小的一個展開，即展開AC（3）結(jié)點，得到ACB（8）、ACD（16）、ACE（13）三個結(jié)點，并把結(jié)點AC標(biāo)記為已展開；3、 再從未展開的所有結(jié)點中找出距離最小的一個展開，即展開AB（7）結(jié)點，得到ABC（12）、ABD（20）、ABE（19）三個結(jié)點，并把結(jié)點

7、AB標(biāo)記為已展開；4、 再次從未展開的所有結(jié)點中找出距離最小的一個展開，即展開ACB（8）結(jié)點，；5、 每次展開所有未展開的結(jié)點中距離最小的那個結(jié)點，直到展開的新結(jié)點中出現(xiàn)目標(biāo)情況（結(jié)點含有5個字母）時，即得到了結(jié)果。,最短路徑問題的求解,小結(jié)： 由上可見，啟發(fā)式搜索和等代價搜索法并沒有象寬度優(yōu)先搜索一樣展開所有結(jié)點，只是根據(jù)某一原則（或某一估價函數(shù)值）每次展開距離A點最近的那個結(jié)點（或是估價函數(shù)計算出的最可能的那個結(jié)點），反復(fù)下去即可最終得到答案。雖然中途有時也展開了一些并不是答案的結(jié)點，但這種展開并不是大規(guī)模的，不是全部展開，因而耗時要比寬度優(yōu)先搜索小得多。,最短路徑問題的求解,例2、題目

8、基本同例1，現(xiàn)在把權(quán)定義成距離，現(xiàn)在要求A點到E點的最短路徑，但并不要求每個城市都要走一遍。,例1、假設(shè)A、B、C、D、E各個城市之間旅費如下圖紅色數(shù)字所示。某人想從城市A出發(fā)游覽各城市一遍，而所用旅費最少，試編程輸出結(jié)果。,問題分析既然不要求每個點都要走一遍，只要距離最短即可，那么普通的寬度優(yōu)先搜索已經(jīng)沒有什么意義了，實際上就是窮舉。那么等代價搜索能不能再用在這題上呢？答案是肯定的，但到底搜索到什么時候才能得到答案呢？這可是個很荊手的問題。是不是搜索到一個結(jié)點是以E結(jié)束時就停止呢？顯然不對。那么是不是要把所有以E為結(jié)束的結(jié)點全部搜索出來呢？這簡直就是寬度優(yōu)先搜索了，顯然不對。實際上，應(yīng)該是搜

9、索到：當(dāng)我們確定將要展開的某個結(jié)點（即所有未展開的結(jié)點中距離最小的那個點）的最后一個字母是E時，這個結(jié)點就是我們所要求的答案！因為比這個結(jié)點大的點再展開得到的解顯然不可能比這個結(jié)點優(yōu)！ 那么，除了等代價搜索外，有沒有其它辦法了呢？下面就介紹這種求最短路徑問題的其它幾種成熟算法。,最短路徑問題的求解,四、寬度優(yōu)先搜索+剪枝 搜索之所以低效，是因為在搜索過程中存在著大量的重復(fù)和不必要的搜索。因此，提高搜索效率的關(guān)鍵在于減少無意義的搜索。假如在搜索時已經(jīng)搜出從起點A到點B的某一條路徑的長度是X，那么我們就可以知道，從A到B的最短路徑長度必定X，因此，其他從A到B的長度大于或等于X的路徑可以一律剔除。

10、具體實現(xiàn)時，可以開一個數(shù)組h1.n，n是結(jié)點總數(shù)，hi表示從起點到結(jié)點i的最短路徑長度。 算法流程如下： 1、 初始化： 將起點start入隊，hstart:=0，hk:=maxlongint(1=k=n，且kstart)。 2、repeat 取出隊頭結(jié)點賦給t； while t有相鄰的結(jié)點沒被擴展 begin t擴展出新的結(jié)點newp； 如果 ht+wt,newp hnewp， 則將newp入隊，把hnewp的值更新為ht+wt,newp； End until 隊列空；,最短路徑問題的求解,五、迭代法 該算法的中心思想是：任意兩點i,j間的最短距離（記為Dij）會等于從i點出發(fā)到達(dá)j點的以任

11、一點為中轉(zhuǎn)點的所有可能的方案中，距離最短的一個。即：Dij = min Dij , Dik+Dkj ，1Dk+gk,j then begin Dj:= Dk+gk,j; c:=true; end; Until not c； 這種算法是產(chǎn)生這樣一個過程：不斷地求一個數(shù)字最短距離矩陣中的數(shù)據(jù)的值，而當(dāng)所有 數(shù)據(jù)都已經(jīng)不能再變化時，就已經(jīng)達(dá)到了目標(biāo)的平衡狀態(tài)，這時最短距離矩陣中的值就是對應(yīng) 的兩點間的最短距離。,最短路徑問題的求解,六、動態(tài)規(guī)劃 動態(tài)規(guī)劃算法已經(jīng)成為了許多難題的首選算法。某些最短路徑問題也可以用動態(tài)規(guī)劃來解決，通常這類最短路徑問題所對應(yīng)的圖必須是有向無回路圖。因為如果存在回路，動態(tài)規(guī)

12、劃的無后效性就無法滿足。 我們知道，動態(tài)規(guī)劃算法與遞歸算法的不同之處在于它們的算法表達(dá)式： 遞歸：類似f(n)=x1*f(n-1)+x2*f(n-2)，即可以找到一個確定的關(guān)系的表達(dá)式；動態(tài)規(guī)劃：類似f(n)=min(f(n-1)+x1,f(n-2)+x2)，即我們無法找到確定關(guān)系的表達(dá)式，只能找到這樣一個不確定關(guān)系的表達(dá)式，f(n)的值是動態(tài)的，隨著f(n-1),f(n-2)等值的改變而確定跟誰相關(guān)。為了給問題劃分階段，必須對圖進行一次拓?fù)渑判?，然后按照拓?fù)渑判虻慕Y(jié)果來動態(tài)規(guī)劃。 譬如，有如下兩個有向圖：,最短路徑問題的求解,右圖因為存在回路而不能用動態(tài)規(guī)劃。而左圖是無回路的，所以可以用動態(tài)

13、規(guī)劃解決。 對左圖拓?fù)渑判?，得到的序列是A、B、D、C、E。 設(shè)F(E)表示從A到E的最短路徑長度，然后按照拓?fù)湫蛄械南群箜樞蜻M行動態(tài)規(guī)劃： F(A)=0 F(B)=min F(A) +3=3 F(D)=min F(A)+8, F(B)+2 =5 F(C)=min F(B)+9, F(D)+5 =10 F(E)=min F(D)+1, F(C)+4 =6 總的式子是：F(i)=min F(k)+dis(i,k) ，k與i必須相連，且在拓?fù)湫蛄兄?，k在i之前。,最短路徑問題的求解,七、標(biāo)號法標(biāo)號法是一種非常直觀的求最短路徑的算法，單從分析過程來看，我們可以用一個數(shù)軸簡單地表示這種算法：1、 以A

14、點為0點，展開與其相鄰的點，并在數(shù)軸中標(biāo)出。,2、因為C點離起點A最近，因此可以斷定C點一定是由A直接到C點這條路徑是最短的（因為A、C兩點間沒有其它的點，所以C點可以確定是由A點直接到達(dá)為最短路徑）。因而就可以以已經(jīng)確定的C點為當(dāng)前展開點，展開與C點想連的所有點A、B、D、E。,3、由數(shù)軸可見，A與A點相比，A點離原點近，因而保留A點，刪除A點，相應(yīng)的，B、B點保留B點，D、D保留D，E、E保留E，得到下圖：,最短路徑問題的求解,4、此時再以離原點最近的未展開的點B聯(lián)接的所有點，處理后，再展開離原點最近未展開的D點，處理后得到如下圖的最終結(jié)果：,5、由上圖可以得出結(jié)論：點C、B、D、E就是點

15、A到它們的最短路徑（注意：這些路徑并不是經(jīng)過了所有點，而是只經(jīng)過了其中的若干個點，而且到每一個點的那條路徑不一定相同）。因而A到E的最短距離就是13。至于它經(jīng)過了哪幾個點大家可在上述過程中加以記錄即可。,最短路徑問題的求解,八、Dijkstra算法（從一個頂點到其余各頂點的最短路徑，單源最短路徑）,例3、如下圖，假設(shè)C1,C2,C3,C4,C5,C6是六座城市，他們之間的連線表示兩城市間有道路相通，連線旁的數(shù)字表示路程。請編寫一程序，找出C1到Ci的最短路徑(2i6)，輸出路徑序列及最短路徑的路程長度。,最短路徑問題的求解,問題分析 對于一個含有n個頂點和e條邊的圖來說，從某一個頂點Vi到其余

16、任一頂點Vj的最短路徑，可能是它們之間的邊（Vi，Vj），也可能是經(jīng)過k個中間頂點和k+1條邊所形成的路徑(1kn-2)。下面給出解決這個問題的Dijkstra算法思想。,設(shè)圖G用鄰接矩陣的方式存儲在GA中，GAi,j=maxint表示Vi，Vj是不關(guān)聯(lián)的，否則為權(quán)值（大于0的實數(shù)）。設(shè)集合S用來保存已求得最短路徑的終點序號，初始時S=Vi表示只有源點，以后每求出一個終點Vj，就把它加入到集合中并作為新考慮的中間頂點。設(shè)數(shù)組dist1.n用來存儲當(dāng)前求得的最短路徑，初始時Vi，Vj如果是關(guān)聯(lián)的，則distj等于權(quán)值，否則等于maxint，以后隨著新考慮的中間頂點越來越多，distj可能越來越小

17、。再設(shè)一個與dist對應(yīng)的數(shù)組path1.n用來存放當(dāng)前最短路徑的邊，初始時為Vi到Vj的邊，如果不存在邊則為空。,執(zhí)行時，先從S以外的頂點（即待求出最短路徑的終點）所對應(yīng)的dist數(shù)組元素中，找出其值最小的元素（假設(shè)為distm），該元素值就是從源點Vi到終點Vm的最短路徑長度，對應(yīng)的pathm中的頂點或邊的序列即為最短路徑。接著把Vm并入集合S中，然后以Vm作為新考慮的中間頂點，對S以外的每個頂點Vj，比較distm+GAm,j的distj的大小，若前者小，表明加入了新的中間頂點后可以得到更好的方案，即可求得更短的路徑，則用它代替distj，同時把Vj或邊（Vm，Vj）并入到pathj中。

18、重復(fù)以上過程n-2次，即可在dist數(shù)組中得到從源點到其余各終點的最段路徑長度，對應(yīng)的path數(shù)組中保存著相應(yīng)的最段路徑。,對于上圖，采用Dijkstra算法找出C1到Ci之間的最短路徑(2i6)的過程如下：,最短路徑問題的求解,初始時：,第一次：選擇m=2，則S=C1,C2，計算比較dist2+GA2,j與distj的大小,第二次：選擇m=3，則S=C1,C2,C3，計算比較dist3+GA3,j與distj的大小,第三次：選擇m=4，S=C1,C2,C3,C4，計算比較dist4+GA4,j與distj的大小,最短路徑問題的求解,第四次：選擇m=5，則S=C1,C2,C3,C4,C5，計算

19、比較dist5+GA5,j與distj的大小,因為該圖的度n=6，所以執(zhí)行n-2=4次后結(jié)束，此時通過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不在集合中，反

20、之，sj=1表示頂點Vj已在集合中）。 Procedure Dijkstra(GA,dist,path,i)； 表示求Vi到圖G中其余頂點的最短路徑，GA為圖G的鄰接矩陣，dist和path為變量型參數(shù)， 其中path的基類型為集合 Begin For j:=1 To n Do Begin 初始化 If ji Then sj:=0 Else sj:=1； distj:=GAi,j； If distjmaxint Then pathj:=i+j Else pathj:= ； End；,最短路徑問題的求解,For k:=1 To n-2 Do Begin w:=maxint；m:=i； For j

21、:=1 To n Do 求出第k個終點Vm If (sj=0) and (distji Then sm:=1 else exit； 若條件成立，則把Vm加入到S中， 否則退出循環(huán)，因為剩余的終點，其最短路徑長度均為maxint，無需再計算下去 For j:=1 To n Do 對sj=0的更優(yōu)元素作必要修改 If (sj=0) and (distm+GAm,jdistj) Then Begin Distj:=distm+GAm,j；pathj:=pathm+j；End； End； End；,最短路徑問題的求解,九、Floyd算法 例4、求任意一對頂點之間的最短路徑。,問題分析 這個問題的解法有

22、兩種：一是分別以圖中的每個頂點為源點共調(diào)用n次Dijkstra算法，這種算法的時間復(fù)雜度為O（n3）；另外還有一種算法：Floyd算法，它的思路簡單，但時間復(fù)雜度仍然為O（n3），下面介紹Floyd算法。 設(shè)具有n個頂點的一個帶權(quán)圖G的鄰接矩陣用GA表示，再設(shè)一個與GA同類型的表示每對頂點之間最短路徑長度的二維數(shù)組A，A的初值等于GA。Floyd算法需要在A上進行n次運算，每次以Vk（1kn）作為新考慮的中間點，求出每對頂點之間的當(dāng)前最短路徑長度，最后依次運算后，A中的每個元素Ai，j就是圖G中從頂點Vi到頂點Vj的最短路徑長度。再設(shè)一個二維數(shù)組P1.n,1.n，記錄最短路徑，其元素類型為集合

23、類型set of 1.n。 Floyd算法的具體描述如下：,最短路徑問題的求解,Procedure Floyd(GA，A，P)； Begin For i:=1 To n Do 最短路徑長度數(shù)組和最短路徑數(shù)組初始化 For j:=1 To n Do Begin Ai,j:=GAi,j； If Ai,jmaxint Then pi,j:=i+j Else pi,j:= ； End； For k:=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；無需計算，直接進入下

24、一輪循環(huán) If Ai,k+Ak,jAi,j Then Begin 找到更短路徑、保存 Ai,j：= Ai,k+Ak,j； Pi,j：= Pi,k+Pk,j； End； End； End；,最短路徑問題的求解,總結(jié)與思考： 最短路徑問題的求解還不止這幾種算法，比如還有分枝定界等等，而且大家也可以創(chuàng)造出各種各樣的新算法來。不同的最短路徑問題到底用哪種算法，以及還需要對該種算法作什么改動，是非常重要的，這種能力往往是很多同學(xué)所欠缺的，這需要大家在平常的訓(xùn)練中多做這類題目，還要多總結(jié)，以達(dá)到熟能生巧的境界。 在學(xué)習(xí)完最短路徑后，有沒有人想到：能不能修改這些算法，實現(xiàn)求最長路徑的問題呢？ 這種發(fā)散性的思

25、維是值得稱贊的，對于不存在回路的有向圖，這種算法是可行的。但需要提醒的是：如果有向圖出現(xiàn)了回路，按照最長路徑的思想和判斷要求，則計算可能沿著回路無限制的循環(huán)下去。 這就引出了一個問題：如何判斷一個有向圖中是否存在回路？可以用bfs或dfs在搜的過程檢查這個點是否在前面出現(xiàn)過；當(dāng)然也可以用拓?fù)渑判蛩惴ā?最短路徑問題的求解,SERCOI工程組是一個講究效率的工程小組。為了規(guī)劃和管理的方便，他們將一個工程分為若干個項目，每個項目都可以獨立進行。所有項目都工作完畢時，整個工程也就完成了。每個項目都需要一定的工作時間。工程最后總耗時是從第一個項目開始到最后一個項目結(jié)束的這段時間。 各個項目之間可能存在也可以不存在相互制約關(guān)系。如果