算法合集之最短路算法及其應用(共30張PPT)精選

算法合集之最短路(duǎnlù)算法及其應用第一頁，共30頁。最短路(duǎnlù)問題是圖論中的核心問題之一，它是許多更深層算法的基礎。同時，該問題有著大量的生產(chǎn)實際的背景。不少問題從表面上看與最短路(duǎnlù)問題沒有什么關系，卻也可以歸結(jié)為最短路(duǎnlù)問題。乘汽車旅行的人總希望找出到目的地盡可能短的行程(xíngchéng)。如果有一張地圖并在地圖上標出了每對十字路口之間的距離，如何找出這一最短行程(xíngchéng)？一個在生活中常見(chánɡjiàn)的例子是:第二頁，共30頁。一種可能的方法是枚舉出所有路徑，并計算(jìsuàn)出每條路徑的長度，然后選擇最短的一條。然而(ránér)我們很容易看到，即使不考慮含回路的路徑，依然存在數(shù)以百萬計的行車路線!實際上，其中絕大多數(shù)路線我們(wǒmen)是沒必要考慮的。這時候，我們應該用一種系統(tǒng)的方法來解決問題，而不是通常人們所用的湊的方法和憑經(jīng)驗的方法。第三頁，共30頁。ENQUEUE(Q,s)最短路(duǎnlù)問題是圖論中的核心問題之一，它是許多更深層算法的基礎。Bellman-Ford第二十七頁，共30頁。剩下的工作就是對圖G使用Dijkstra算法求到的最短路長。定義(dìngyì)u到v間最短路徑的權為：例二網(wǎng)絡提速(經(jīng)典(jīngdiǎn)問題)第二十九頁，共30頁。例二網(wǎng)絡(wǎngluò)提速(經(jīng)典問題)完全通過這題簡直是輕而易舉。第二十四頁，共30頁。Bellman-Ford算法對于所有(suǒyǒu)最短路長存在的圖都適用，但是效率常常不盡人意。這道題棘手的地方在于標號已經(jīng)不是一維，而是二維，因此不再有全序關系。簡證：我們每次選擇在集合V-S中具有最小最短路徑估計的結(jié)點u，因為我們約定所有的邊權值非負，所以有可能對結(jié)點u進行松弛操作的結(jié)點必不在集合V-S中（否則與結(jié)點u的定義矛盾），因此只會在集合S中。一個(yīɡè)明顯的反例是：定義(dìngyì)在最短路問題(wèntí)中，給出的是一有向加權圖G=(V,E)，在其上定義的加權函數(shù)W:E→R為從邊到實型權值的映射。路徑P=(v0,v1,……,vk)的權是指其組成邊的所有權值之和：定義(dìngyì)u到v間最短路徑的權為：從結(jié)點u到結(jié)點v的最短路徑定義為權的任何路徑。第四頁，共30頁。在乘車旅行的例子中，我們可以把公路(gōnglù)地圖模型化為一個圖：結(jié)點表示路口，邊表示連接兩個路口的公路(gōnglù)，邊權表示公路(gōnglù)的長度。我們的目標是從起點出發(fā)找一條到達目的地的最短路徑。邊的權常被解釋為一種度量方法，而不僅僅是距離。它們常常被用來表示時間(shíjiān)、金錢、罰款、損失或任何其他沿路徑線性積累的數(shù)量形式。第五頁，共30頁。重要(zhòngyào)性質(zhì)定理1(最優(yōu)子結(jié)構(gòu))給定(ɡěidìnɡ)有向加權圖G=(V,E)，設P=<v1,v2,…,vk>為從結(jié)點v1到結(jié)點vk的一條最短路徑，對任意i,j有i<=j<=k，設Pij=<vi,vi+1,…,vj>為從vi到vj的P的子路徑,則Pij是從vi到vj的一條最短路徑。證明：我們把路徑P分解為<v1,v2,…,vi,vi+1,…vj,…vk>。則w(P)=w(P1i)+w(Pij)+w(Pjk)。現(xiàn)在假設從vi到vj存在一路徑P’ij，且w(P’ij)<w(Pij)，則將P中的路徑Pij=(vi,vi+1,…vj)替換成P’ij，依然是從v1到vk的一條(yītiáo)路徑，且其權值w(P1i)+w(P’ij)+w(Pjk)小于w(P)，這與前提P是從v1到vk的最短路徑矛盾。（證畢）第六頁，共30頁。推論(tuīlùn)推論1.1給定有向加權圖G=(V,E),源點為s，則對于(duìyú)所有邊(u,v)E，有：證明：從源點s到結(jié)點v的最短路徑(lùjìng)P的權不大于從s到v的其它路徑(lùjìng)的權。特別地，路徑(lùjìng)P的權也不大于某特定路徑(lùjìng)的權，該特定路徑(lùjìng)為從s到u的最短路徑(lùjìng)加上邊(u,v)。（證畢）第七頁，共30頁。松弛(sōnɡchí)技術INITIALIZE-SINGLE-SOURCE(G,s)1.For每個結(jié)點(jiédiǎn)vV[G]2.Dod[v]←3.[v]←NIL4.d[s]0對每個結(jié)點vV，我們設置一屬性d[v]來描述(miáoshù)從源s到v的最短路徑的權的上界，稱之為最短路徑估計。我們通過下面的過程對最短路徑估計和先輩初始化。RELAX(u,v,w)1.Ifd[v]>d[u]+w(u,v)2.Thend[v]←d[u]+w(u,v)3.[v]←u

一次松弛操作可以減小最短路徑的估計值d[v]并更新v的先輩域[v]第八頁，共30頁。常用(chánɡyònɡ)算法一、Dijkstra算法(suànfǎ)二、Bellman-Ford算法(suànfǎ)三、SPFA算法第九頁，共30頁。Dijkstra算法(suànfǎ)Dijkstra算法中設置了一結(jié)點集合S，從源結(jié)點s到集合S中結(jié)點的最終最短路徑的權均已確定，即對所有(suǒyǒu)結(jié)點vS，有d[v]=(s,v)。算法反復挑選出其最短路徑估計為最小的結(jié)點uV-S，把u插入集合S中，并對離開u的所有(suǒyǒu)邊進行松弛。Dijkstra(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,S)2.S3.Q←V[G]4.WhileQ5.Dou←EXTRACT-MIN(Q)6.S←SU{u}7.For每個頂點(dǐngdiǎn)vAdj[u]8.DoRELAX(u,v,w)第十頁，共30頁。Dijkstra算法(suànfǎ)適用(shìyòng)條件:所有邊的權值非負定理2每當結(jié)點u插入集合(jíhé)S時，有d[u]=(s,u)成立。簡證：我們每次選擇在集合V-S中具有最小最短路徑估計的結(jié)點u，因為我們約定所有的邊權值非負，所以有可能對結(jié)點u進行松弛操作的結(jié)點必不在集合V-S中（否則與結(jié)點u的定義矛盾），因此只會在集合S中。又由于我們選取結(jié)點進入S時，S中的結(jié)點已全部進行過松弛操作了，所以d[u]的值不會再發(fā)生改變。因此d[u]=(s,u)。（證畢）效率:用一維數(shù)組來實現(xiàn)優(yōu)先隊列Q，O()，適用于中等規(guī)模的稠密圖二叉堆來實現(xiàn)優(yōu)先隊列Q，O((E+V)logV)，適用于稀疏圖用Fibonacci堆來實現(xiàn)優(yōu)先隊列Q的話，O(VlogV)，可惜編程復雜度過高，理論價值遠大于實用價值第十一頁，共30頁。Bellman-Ford算法(suànfǎ)Bellman-Ford算法運用了松弛技術，對每一結(jié)點vV，逐步減小從源s到v的最短路徑(lùjìng)的估計值d[v]直至其達到實際最短路徑(lùjìng)的權(s,v)，如果圖中存在負權回路，算法將會報告最短路不存在。Bellman-Ford(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.Fori←1to|V[G]|-13.DoFor每條邊(u,v)E[G]4.DoRELAX(u,v,w)5.For每條邊(u,v)E[G]6.DoIfd[v]>d[u]+w(u,v)7.ThenReturnFALSE8.ReturnTRUE第十二頁，共30頁。Bellman-Ford算法(suànfǎ)適用條件:任意(rènyì)邊權為實數(shù)的圖Bellman-Ford算法的思想基于以下事實：“兩點間如果有最短路，那么每個結(jié)點最多經(jīng)過一次。也就是說，這條路不超過n-1條邊?！保ㄈ绻粋€結(jié)點經(jīng)過了兩次，那么我們(wǒmen)走了一個圈。如果這個圈的權為正，顯然不劃算；如果是負圈，那么最短路不存在；如果是零圈，去掉不影響最優(yōu)值）根據(jù)最短路的最優(yōu)子結(jié)構(gòu)（定理1），路徑邊數(shù)上限為k時的最短路可以由邊數(shù)上限為k-1時的最短路“加一條邊”來求，而根據(jù)剛才的結(jié)論，最多只需要迭代n-1次就可以求出最短路。效率:Bellman-Ford算法的運行時間為O(VE)。很多時候，我們的算法并不需要運行|V|-1次就能得到最優(yōu)值。對于一次完整的第3-4行操作，要是一個結(jié)點的最短路徑估計值也沒能更新，就可以退出了。經(jīng)過優(yōu)化后，對于多數(shù)情況而言，程序的實際運行效率將遠離O(VE)而變?yōu)镺(kE)，其中k是一個比|V|小很多的數(shù)。第十三頁，共30頁。SPFA算法(suànfǎ)設立一個先進先出的隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，并且用u點當前的最短路徑估計值對離開u點所指向的結(jié)點v進行松弛操作，如果(rúguǒ)v點的最短路徑估計值有所調(diào)整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結(jié)點來進行松弛操作，直至隊列空為止。SPFA(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.INITIALIZE-QUEUE(Q)3.ENQUEUE(Q,s)4.WhileNotEMPTY(Q)5.Dou←DLQUEUE(Q)6.For每條邊(u,v)E[G]7.Dotmp←d[v]8.Relax(u,v,w)9.If(d[v]<tmp)and(v不在Q中)10.ENQUEUE(Q,v)我們用數(shù)組d記錄每個結(jié)點的最短路徑(lùjìng)估計值，而且用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：第十四頁，共30頁。SPFA算法(suànfǎ)適用條件(tiáojiàn):任意邊權為實數(shù)的圖定理3只要最短路徑存在(cúnzài)，上述SPFA算法必定能求出最小值。證明：每次將點放入隊尾，都是經(jīng)過松弛操作達到的。換言之，每次的優(yōu)化將會有某個點v的最短路徑估計值d[v]變小。所以算法的執(zhí)行會使d越來越小。由于我們假定圖中不存在負權回路，所以每個結(jié)點都有最短路徑值。因此，算法不會無限執(zhí)行下去，隨著d值的逐漸變小，直到到達最短路徑值時，算法結(jié)束，這時的最短路徑估計值就是對應結(jié)點的最短路徑值。（證畢）定理4在平均情況下，SPFA算法的期望時間復雜度為O(E)。證明：上述算法每次取出隊首結(jié)點u，并訪問u的所有臨結(jié)點的復雜度為O(d)，其中d為點u的出度。運用均攤分析的思想，對于|V|個點|E|條邊的圖，點的平均出度為，所以每處理一個點的復雜度為O()。假設結(jié)點入隊次數(shù)為h，顯然h隨圖的不同而不同。但它僅與邊權值分布有關。我們設h=kV，則算法SPFA的時間復雜度為在平均的情況下，可以將k看成一個比較小的常數(shù)，所以SPFA算法在一般情況下的時間復雜度為O(E)。（證畢）第十五頁，共30頁。小結(jié)(xiǎojié)Dijkstra算法的效率高，但是(dànshì)也有局限性，就是對于含負權的圖無能為力。Bellman-Ford算法對于所有(suǒyǒu)最短路長存在的圖都適用，但是效率常常不盡人意。SPFA算法可以說是綜合了上述兩者的優(yōu)點。它的效率同樣很不錯，而且對于最短路長存在的圖都適用，無論是否存在負權。它的編程復雜度也很低，是高性價比的算法。我們應該根據(jù)實際需要，找到時空復雜度和編程復雜度的平衡點，在考場上用最少的時間拿盡可能多的分數(shù)。算法時間復雜度空間復雜度編程復雜度適用范圍Dijkstra O()或O((E+V)logV)O()或O(E+V)簡單或相對復雜不含負權的圖(窄)Bellman-FordO(VE)O(E+V)簡單實數(shù)圖(廣)SPFAO(E)O(E+V)簡單實數(shù)圖(廣)第十六頁，共30頁。例一雙調(diào)路徑(lùjìng)(BOI2002)如今的道路密度越來越大，收費也越來越多，因此選擇最佳路徑是很現(xiàn)實的問題。城市的道路是雙向的，每條道路有固定的旅行時間以及需要支付的費用。路徑由連續(xù)(liánxù)的道路組成?？倳r間是各條道路旅行時間的和，總費用是各條道路所支付費用的總和。同樣的出發(fā)地和目的地，如果路徑A比路徑B所需時間少且費用低，那么我們說路徑A比路徑B好。對于某條路徑，如果沒有其他路徑比它好，那么該路徑被稱為最優(yōu)雙調(diào)路徑。這樣的路徑可能不止一條，或者說根本不存在。給出城市交通網(wǎng)的描述信息，起始點和終點城市，求最優(yōu)雙條路徑的條數(shù)。城市不超過100個，邊數(shù)不超過300，每條邊上的費用和時間都不超過100。題意(tíyì)簡述：第十七頁，共30頁。例一雙調(diào)路徑(lùjìng)(BOI2002)這道題棘手的地方在于標號已經(jīng)不是一維，而是二維，因此不再有全序關系。我們可以采用(cǎiyòng)拆點法，讓d[i,c]表示從s到i費用為c時的最短時間。分析(fēnxī)：算法一：標號設定算法是根據(jù)拓撲順序不斷把臨時標號變?yōu)橛谰脴颂柕?。在這題中，其實，我們并不需要嚴格的拓撲順序，而只需要一個讓標號永久化的理由。拓撲順序能保證標號的永久化，但是還有其他方式。在本題中，標號永久化的條件是：從其他永久標號得不到費用不大于c且時間不大于t的臨時標號（這里利用了費用和時間的非負性），即：所有的“極小臨時標號”都可以永久化。這樣，一個附加的好處是一次把多個臨時標號同時變成永久的。第十八頁，共30頁。例一雙調(diào)路徑(lùjìng)(BOI2002)假設時間上限為t，費用上限為c，城市數(shù)為n，邊數(shù)為m，則每個點上的標號不超過O(nc)個，標號總數(shù)為O(n*n*c)個，每條邊考慮O(nc)次。如果不同頂點(dǐngdiǎn)在同一費用的臨時標號用堆來維護，不同費用的堆又組成一個堆的話，那么建立（或更新）臨時標號的時間為O(mnclognlogc)，總的時間復雜度為O(nnc+mnclognlogc)，本題的規(guī)模是完全可以承受的。實際上由于標號的次數(shù)往往遠小于nnc，程序效率是相當理想的算法(suànfǎ)二：在本題中構(gòu)圖直接用SPFA算法(suànfǎ)。在最壞情況下，費用最大值c為100*100=10000，那么每個點將被拆成10000個點，由于原圖邊數(shù)不超過300，所以我們構(gòu)造的新圖中邊數(shù)不會超過3000000。因此算法(suànfǎ)的時間復雜度是O(k*3000000)。寫出來的程序運行的實際效果非常好，每個數(shù)據(jù)的速度都比官方參考程序（算法(suànfǎ)一）快，有幾個甚至比官方程序快3~4倍！完全通過這題簡直是輕而易舉。這和我們對時間復雜度在理論上的分析是一致的。第十九頁，共30頁。例一雙調(diào)路徑(lùjìng)(BOI2002)兩個算法在空間上是同階的，一樣是O(E)。雖然算法一僅用到二叉堆，并不是特別復雜，但是因為要用兩個堆，建立更新刪除寫起來還是有一定的工作量的。SPFA算法寫起來極其簡單，效率又高，而且(érqiě)適用范圍廣（可以處理含有負權的圖），在很多情況下，是最短路問題上好的選擇。第二十頁，共30頁。例二網(wǎng)絡提速(經(jīng)典(jīngdiǎn)問題)某學校的校園網(wǎng)由n(1<=n<=50)臺計算機組成，計算機之間由網(wǎng)線相連，其中頂點代表計算機，邊代表網(wǎng)線。不同網(wǎng)線的傳輸能力不盡相同?，F(xiàn)學校購買了m(1<=m<=10)臺加速設備，每臺設備可作用于一條(yītiáo)網(wǎng)線，使網(wǎng)線上傳輸信息用時減半。多臺設備可用于同一條(yītiáo)網(wǎng)線，其效果疊加。如何合理使用這些設備，使計算機1到計算機n傳輸用時最少，這個問題急需解決。校方請你編程解決這個問題。題意(tíyì)簡述：第二十一頁，共30頁。例二網(wǎng)絡(wǎngluò)提速(經(jīng)典問題)如圖，若n=5，m=2，則將兩臺(liǎnɡtái)設備分別用于1-3，3-5的線路，傳輸用時可減少為22秒，這是最佳解。3020162410123442531第二十二頁，共30頁。例二網(wǎng)絡提速(tísù)(經(jīng)典問題)讓我們重新描述一下(yīxià)問題：給定含有n個頂點的帶權無向圖，一共可以進行m次操作，每次操作將一條邊的權值除以2。問每次應該對哪條邊進行操作，使得1到n的最短路徑權和最小。

分析(fēnxī)：如果我們把Dijkstra算法直接用在原圖上，得到的是沒有使用任何加速設備頂點1到頂點n的最短路長，不是我們想要的結(jié)果。經(jīng)過簡單的舉例后發(fā)現(xiàn)行不通。能否用增量法做這題呢？就是，我們先求出使用前m-1臺加速設備的最短路長，然后通過枚舉之類算出第m臺設備用在那條邊上，行不行呢？第二十三頁，共30頁。例二網(wǎng)絡(wǎngluò)提速(經(jīng)典問題)一個(yīɡè)明顯的反例是：4081612431如果我們只有一個加速設備的話，顯然將它加在1-2上，那么(nàme)最短路長16是最佳的。但是，我們有兩個的話，將兩個都加在3-4上，則最短路長11是最優(yōu)的。所以要是我們的加速設備增多一臺的話，可能導致前面的所有放置方案都不是最優(yōu)值。第二十四頁，共30頁。例二網(wǎng)絡提速(經(jīng)典(jīngdiǎn)問題)我們注意到一點，就是n和m都很小，特別是m，最大只有(zhǐyǒu)10。直覺和經(jīng)驗告訴我們，應該從數(shù)據(jù)規(guī)模小上面作文章。從簡單情形入手(rùshǒu)往往是解題的捷徑。沒有m值，或者說m=0時，問題的解就是最簡單的最短路徑問題。m值的出現(xiàn)導致了最短路算法的失敗。關鍵是我們不知道應該在哪幾條邊用加速設備，而且每條邊用多少次也不知道。方案與權值的分布還有m值的大小都有莫大的關聯(lián)。我們想想，有無m值的差異在哪，能夠消除嗎？可以的。第二十五頁，共30頁。例二網(wǎng)絡提速(經(jīng)典(jīngdiǎn)問題)構(gòu)造圖G=(V,E)。設原圖(yuántú)，將原圖(yuántú)中的每個頂點vi拆成m+1個頂點，構(gòu)造V使得：對于原圖(yuántú)的每一條邊，注意是無向的，，將它拆成(m+1)(m+2)條有向邊：…………構(gòu)造E使得：最后設定權函數(shù)w。對于，w滿足：