算法合集之最短路算法及其應(yīng)用

算法合集之最短路算法及其應(yīng)用第1頁，共30頁，2023年，2月20日，星期六最短路問題是圖論中的核心問題之一，它是許多更深層算法的基礎(chǔ)。同時(shí)，該問題有著大量的生產(chǎn)實(shí)際的背景。不少問題從表面上看與最短路問題沒有什么關(guān)系，卻也可以歸結(jié)為最短路問題。乘汽車旅行的人總希望找出到目的地盡可能短的行程。如果有一張地圖并在地圖上標(biāo)出了每對十字路口之間的距離，如何找出這一最短行程？一個(gè)在生活中常見的例子是:第2頁，共30頁，2023年，2月20日，星期六一種可能的方法是枚舉出所有路徑，并計(jì)算出每條路徑的長度，然后選擇最短的一條。然而我們很容易看到，即使不考慮含回路的路徑，依然存在數(shù)以百萬計(jì)的行車路線!實(shí)際上，其中絕大多數(shù)路線我們是沒必要考慮的。這時(shí)候，我們應(yīng)該用一種系統(tǒng)的方法來解決問題，而不是通常人們所用的湊的方法和憑經(jīng)驗(yàn)的方法。第3頁，共30頁，2023年，2月20日，星期六定義在最短路問題中，給出的是一有向加權(quán)圖G=(V,E)，在其上定義的加權(quán)函數(shù)W:E→R為從邊到實(shí)型權(quán)值的映射。路徑P=(v0,v1,……,vk)的權(quán)是指其組成邊的所有權(quán)值之和：定義u到v間最短路徑的權(quán)為：從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑定義為權(quán)的任何路徑。第4頁，共30頁，2023年，2月20日，星期六在乘車旅行的例子中，我們可以把公路地圖模型化為一個(gè)圖：結(jié)點(diǎn)表示路口，邊表示連接兩個(gè)路口的公路，邊權(quán)表示公路的長度。我們的目標(biāo)是從起點(diǎn)出發(fā)找一條到達(dá)目的地的最短路徑。邊的權(quán)常被解釋為一種度量方法，而不僅僅是距離。它們常常被用來表示時(shí)間、金錢、罰款、損失或任何其他沿路徑線性積累的數(shù)量形式。第5頁，共30頁，2023年，2月20日，星期六重要性質(zhì)

定理1(最優(yōu)子結(jié)構(gòu))給定有向加權(quán)圖G=(V,E)，設(shè)P=<v1,v2,…,vk>為從結(jié)點(diǎn)v1到結(jié)點(diǎn)vk的一條最短路徑，對任意i,j有i<=j<=k，設(shè)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)?，F(xiàn)在假設(shè)從vi到vj存在一路徑P’ij，且w(P’ij)<w(Pij)，則將P中的路徑Pij=(vi,vi+1,…vj)替換成P’ij，依然是從v1到vk的一條路徑，且其權(quán)值w(P1i)+w(P’ij)+w(Pjk)小于w(P)，這與前提P是從v1到vk的最短路徑矛盾。（證畢）第6頁，共30頁，2023年，2月20日，星期六推論推論1.1給定有向加權(quán)圖G=(V,E),源點(diǎn)為s，則對于所有邊(u,v)E，有：證明：從源點(diǎn)s到結(jié)點(diǎn)v的最短路徑P的權(quán)不大于從s到v的其它路徑的權(quán)。特別地，路徑P的權(quán)也不大于某特定路徑的權(quán)，該特定路徑為從s到u的最短路徑加上邊(u,v)。（證畢）第7頁，共30頁，2023年，2月20日，星期六松弛技術(shù)INITIALIZE-SINGLE-SOURCE(G,s)1.For每個(gè)結(jié)點(diǎn)vV[G]2.Dod[v]←3.[v]←NIL4.d[s]0對每個(gè)結(jié)點(diǎn)vV，我們設(shè)置一屬性d[v]來描述從源s到v的最短路徑的權(quán)的上界，稱之為最短路徑估計(jì)。我們通過下面的過程對最短路徑估計(jì)和先輩初始化。RELAX(u,v,w)1.Ifd[v]>d[u]+w(u,v)2.Thend[v]←d[u]+w(u,v)3.[v]←u

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

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