最短路徑算法最短路徑算法圖的最短路徑多階圖最短路徑算法Dijkstra最短路徑算法Bellman-Ford最短路徑算法Floyd-Warshall最短路徑算法2圖的最短路徑(1)由有向圖(directedgraphordigraph)中的某個(gè)頂點(diǎn)或節(jié)點(diǎn)(vertexornode)v到圖中的另一節(jié)點(diǎn)u，若v到u之間存在一條路徑(path)，則路徑中所經(jīng)過的邊(edgeorarc)的權(quán)值或加權(quán)(weight)的總合稱為路徑的成本(cost)或距離(distance)。所有路徑中具有最小成本的稱為最短路徑(shortestpath)。范例:在左方的圖中，節(jié)點(diǎn)s到節(jié)點(diǎn)b的最短路徑為s->c->b

在右方的圖中，節(jié)點(diǎn)s到節(jié)點(diǎn)b沒有最短路徑，因?yàn)榇嬖?/p>

負(fù)(成本)循環(huán)b->d->b->d->….

3圖的最短路徑(2)由于最短路徑具有許多應(yīng)用，因此有許多求取最短路徑的演算法，著名的算法包括：(1)

多階圖最短路徑算法(使用動(dòng)態(tài)規(guī)劃解題策略)(2)

Dijkstra算法(使用貪婪解題策略)(3)Bellman-Ford算法(使用動(dòng)態(tài)規(guī)劃解題策略)(4)Floyd-Warshall算法(使用動(dòng)態(tài)規(guī)劃解題策略)45例:找出從v0到v3的最短路徑(shortestpath)。貪婪算法可以解決此問題。最短路徑:1+2+4=7有些問題可以使用貪婪算法解決6有些問題不能使用貪婪算法解決例：從多階圖(multi-stagegraph)中找出v0到v3的最短路徑。貪婪算法:v0v1,2v2,1v3=23最佳解:v0v1,1v2,2v3=7貪婪算法無法解決此問題。這是因?yàn)椴煌A(stage)的決策會(huì)影響到其他階的決策。復(fù)習(xí):

動(dòng)態(tài)規(guī)劃與貪婪算法之比較比較:二者都是透過一系列的決策以解決最佳化問題，但是有以下的不同點(diǎn):在貪婪算法中，任何決策都是獨(dú)立(independent)的，都只要考慮區(qū)域最佳解(locallyoptimal)。這些區(qū)域最佳解最后會(huì)加成為全域最佳解(globallyoptimalsolution)。在動(dòng)態(tài)規(guī)劃算法中，決策是相依的(dependent)。每個(gè)決策必須考慮其他決策所產(chǎn)生的結(jié)果才能求得全域最佳解(globallyoptimalsolution)。7

多階圖最短路徑算法8多階圖最短路徑問題

(multi-stagegraph

shortestpathproblem)多階圖G=(V,E)是有向圖(directedgraph)，其節(jié)點(diǎn)被分割成k

2

個(gè)兩兩互斥(mutuallydisjoint)集合Pi,1

i

k，每一個(gè)集合Pi,1

ik被定義為圖中的第i階(stage)。此外，每個(gè)邊(x,y)E滿足xPi

且yPi+i,1

i<k，且每個(gè)邊都有一個(gè)加權(quán)(weight)wx,y。

多階圖中第1階集合P1

只包含一節(jié)點(diǎn)，稱為源點(diǎn)或來源點(diǎn)(source);第k階集合Pk

也只包含一節(jié)點(diǎn)，稱為標(biāo)點(diǎn)或目標(biāo)點(diǎn)(target)。多階圖最短路徑問題是要找出由源點(diǎn)(source)s到標(biāo)點(diǎn)(target)

t的最小成本路徑(minimum-costpath)或最短路徑(shortestpath)。

9多階圖范例Stage1Stage2Stage3Stage410貪婪算法無法解決

多階圖最小成本路徑問題例如：貪婪算法無法解決此問題:SADT1+4+18=23.最短路徑為:

S->C->F->T，成本為5+2+2=9.就像分期買商品一樣，都分三期付款，最終都可以得到商品的產(chǎn)權(quán)。有的付款方式第一期要繳1萬，有的要繳2萬，有的要繳5萬。但是依照不同的第一期繳法，則在第二期甚或第三期都有不同的繳款選擇，而造成繳款總額的不同。11動(dòng)態(tài)規(guī)劃遞回關(guān)系(1)d(S,T)=min{1+d(A,T),2+d(B,T),5+d(C,T)}12動(dòng)態(tài)規(guī)劃遞回關(guān)系(2)d(A,T)=min{4+d(D,T),11+d(E,T)}=min{4+18,11+13}=22.13動(dòng)態(tài)規(guī)劃遞回關(guān)系(3)(下式省略邊界條件值d(T,T)=0)d(B,T)=min{9+d(D,T),5+d(E,T),16+d(F,T)}=min{9+18,5+13,16+2}=18.d(C,T)=min{2+d(F,T)}=2+2=4.d(S,T)=min{1+d(A,T),2+d(B,T),5+d(C,T)}=min{1+22,2+18,5+4}=9.14動(dòng)態(tài)規(guī)劃多階圖最短路徑算法

15Dijkstra最短路徑算法16E.W.Dijkstra(1930年5月11日－2002年8月6日)生于荷蘭鹿特丹在1972年獲得圖靈獎(jiǎng)(TuringAward)2002年，Dijkstra獲得了ACMPODC(PrinciplesofDistributedComputing)最具影響力論文獎(jiǎng)(InfluentialPaperAward)，以表彰他在分散式計(jì)算(distributedcomputing)領(lǐng)域中關(guān)于自我穩(wěn)定(selfstabilization)計(jì)算模式的貢獻(xiàn)。為了紀(jì)念他，這個(gè)每年一度獎(jiǎng)項(xiàng)也在此后被更名為Dijkstra獎(jiǎng)(DijkstraPrize)Dijkstra最短路徑算法設(shè)計(jì)者Source:http:///wiki/Edsger_W._DijkstraCreativeCommonsAttribution-ShareAlike3.0UnportedAuthor:HamiltonRichards17Attribution2.0Generic

(CCBY2.0)ElliottBrownDijkstra最短路徑算法

“OnemorningIwasshoppinginAmsterdamwithmyyoungfiancée,andtired,wesatdownonthecaféterracetodrinkacupofcoffeeandIwasjustthinkingaboutwhetherIcoulddothis,andIthendesignedthealgorithmfortheshortestpath.AsIsaid,itwasa20-minuteinvention.Infact,itwaspublishedin1959,threeyearslater.”ThomasJ.Misa(Editor),"AnInterviewwithEdsgerW.Dijkstra,"CommunicationsoftheACM53(8):41–47,2010.

是喝咖啡時(shí)20分鐘想出的發(fā)明Source:/photos/ell-r-brownin/photolist-18Dijkstra最短路徑算法介紹Dijkstra算法:Dijkstra算法屬于求取單一(single)源(source)節(jié)點(diǎn)至全部(all)終(destination)節(jié)點(diǎn)的單源節(jié)點(diǎn)至全部節(jié)點(diǎn)之一至全(one-to-all)最短路徑算法。Dijkstra算法只能用在所有的邊都是非負(fù)邊(non-negativeweightededge)的圖。因?yàn)樨?fù)邊有可能產(chǎn)生負(fù)循環(huán)，因而無法產(chǎn)生正確的最短路徑，而Dijkstra算法并無法檢查給定的圖是否有負(fù)循環(huán)。Dijkstra最短路徑算法采用貪婪策略解決問題，每次都挑選一個(gè)目前可以由源節(jié)點(diǎn)抵達(dá)之距離最小的節(jié)點(diǎn)，再往外調(diào)整其鄰居節(jié)點(diǎn)之由源節(jié)點(diǎn)抵達(dá)的最短距離。在經(jīng)過n次(n為節(jié)點(diǎn)個(gè)數(shù))的節(jié)點(diǎn)選擇之後(包括第一次選出由源節(jié)點(diǎn)到達(dá)源節(jié)點(diǎn)距離為0的最短距離之選擇)，則算法可以求得由單一源節(jié)點(diǎn)到達(dá)所有節(jié)點(diǎn)的最短距離，也就是一至全(one-to-all)最短路徑距離。19Dijkstra最短路徑算法AlgorithmDijkstra最短路徑算法Input：給定一個(gè)非負(fù)加權(quán)有向圖(non-negativeweighteddigraph)G=(V,E)，及一個(gè)來源(source)節(jié)點(diǎn)s。G各邊的加權(quán)值以w[x][y]表示，其中x及y為邊的二個(gè)節(jié)點(diǎn)。

Output：陣列d，其中d[u]記錄每一個(gè)節(jié)點(diǎn)u由s到u的最短路徑距離(累積邊加權(quán))。d[s]←0;d[v]←∞foreachnodev,vV,v≠s將每一個(gè)節(jié)點(diǎn)v依照d[v]值加入優(yōu)先隊(duì)列QwhileQ≠

do

自Q中移出具有最小d[u]值之節(jié)點(diǎn)u

foreveryv,(u,v)

Edo\\此循環(huán)針對(duì)每一個(gè)由u可以直接到達(dá)的相鄰節(jié)點(diǎn)v執(zhí)行

ifd[v]

>

d[u]+w[u][v]then

d[v]←d[u]+w[u][v]returnd20Dijkstra最短路徑算法

如何記錄所有的路徑?Dijkstra算法使用陣列d，讓其中d[u]記錄每一個(gè)節(jié)點(diǎn)u由s到u的最短路徑距離。若要讓Dijkstra算法也能夠求出每一條最短路徑所經(jīng)過的每一個(gè)節(jié)點(diǎn)，則我們要將每一節(jié)點(diǎn)在最短路徑中的前一節(jié)點(diǎn)紀(jì)錄下來，其作法為增加一個(gè)陣列pred(代表predecessor，前行者)來記錄最短路徑中的每一個(gè)節(jié)點(diǎn)的前一節(jié)點(diǎn)。并將Dijkstra算法之if敘述修改如下：if(d[v]

>

d[u]+w[u][v])then

d[v]←d[u]+w[u][v]

pred[v]←u//意思為在最短路徑中節(jié)點(diǎn)v的前一節(jié)點(diǎn)為u21Dijkstra算法執(zhí)行范例22Dijkstra最短路徑算法復(fù)雜度23復(fù)習(xí):使用二元堆積實(shí)作優(yōu)先佇之時(shí)間復(fù)雜度為初始化O(n)、插入新元素與提取最小元素操作的時(shí)間復(fù)雜度為O(logn)。假設(shè)G一共有n個(gè)節(jié)點(diǎn)，m個(gè)邊(也就是|V|=n,|E|=m)行1.初始化d:O(n)行2.建立包含每一個(gè)節(jié)點(diǎn)的優(yōu)先隊(duì)列Q:

O(n)行3.while循環(huán)每次迭代會(huì)自Q中次移出一個(gè)節(jié)點(diǎn)，因此會(huì)執(zhí)行n次迭代行4.使用O(logn)時(shí)間自Q中移出最小d[u]值之節(jié)點(diǎn)u行5.for回圈在整個(gè)算法的執(zhí)行過程中一共執(zhí)行m次迭代行7.使用O(logn)時(shí)間根據(jù)新的d[v]值更新v在Q中的位置(先刪除v再新增v)因此總時(shí)間復(fù)雜度為O((n+m)logn)=O((|V|+|E|)log|V|)

Bellman-Ford

最短路徑算法24Bellman-Ford最短路徑算法介紹與Dijkstra算法相同，Bellman-Ford算法也是屬于求取單一源節(jié)點(diǎn)至全部終節(jié)點(diǎn)的一至全最短路徑算法。但是與Dijkstra算法不同的是，Bellman-Ford算法可以檢查圖是否有負(fù)加權(quán)循環(huán)(cycle)，因此在具有負(fù)加權(quán)(negativeweight)邊的圖也可以正確的執(zhí)行。25Bellman-Ford最短路徑算法介紹(續(xù))Bellman-Ford最短路徑算法采用動(dòng)態(tài)規(guī)劃策略解決問題。起始狀態(tài)下，算法設(shè)定0-邊路徑(0-edgepath)最短路徑起始值，也就是由源節(jié)點(diǎn)不能經(jīng)過任何邊的最短路徑，此時(shí)只有由源節(jié)點(diǎn)到源節(jié)點(diǎn)的路徑為0，而由源節(jié)點(diǎn)到其他節(jié)點(diǎn)的路徑都不存在，其值設(shè)為無窮大，等待稍后的向下調(diào)整。26Bellman-Ford最短路徑算法介紹(續(xù))然后算法一開始在第1次迭代先針對(duì)每個(gè)邊，求出所有由源節(jié)點(diǎn)可到達(dá)的，屬于最多為1-邊路徑(1-edgepath)的最短路徑；然後基這個(gè)結(jié)果，在第2次迭代針對(duì)每個(gè)邊，求出所有由源節(jié)點(diǎn)可到達(dá)的，屬于最多為2-邊路徑(2-edgepath)的最短路徑…。依此類推，在第n-1次迭代則可以求出所有由源節(jié)點(diǎn)可到達(dá)的，屬於最多為(n-1)-邊路徑((n-1)-edgepath)的最短路徑。因?yàn)榫遪個(gè)節(jié)點(diǎn)的圖最長(zhǎng)的路徑具有n-1個(gè)邊，因此第n-1次迭代求出的路徑已經(jīng)是所有由源節(jié)點(diǎn)可到達(dá)其他節(jié)點(diǎn)的最短路徑了。27Bellman-Ford最短路徑算法AlgorithmBellman-Ford最短路徑算法Input:給定一個(gè)加權(quán)有向圖(weighteddigraph)G=(V,E)，及一個(gè)來源(source)節(jié)點(diǎn)s。G各邊的加權(quán)值以w[x][y]表示，其中x及y為邊的二個(gè)節(jié)點(diǎn)。Output:對(duì)每一個(gè)頂點(diǎn)u而言，傳回一個(gè)由s到u的最短路徑距離(累積邊加權(quán))d[u]。d[s]←0;d[u]←∞foreachu≠sfori←1to|V|-1dofor每一個(gè)G的邊(u,v)

doifd[v]>d[u]+w[u][v]thend[v]←d[u]+w[u][v]for每一個(gè)G的邊(u,v)do//檢查是否存在負(fù)循環(huán)(negative-weightcycle)ifd[v]>d[u]+w[u][v]then

returnfalse//代表存在負(fù)循環(huán)，無法產(chǎn)生正確最短路徑returnd28Bellman-Ford最短路徑算法復(fù)雜度假設(shè)G一共有n個(gè)節(jié)點(diǎn)，m個(gè)邊(也就是|V|=n,|E|=m)行2-5的外層for循環(huán)一共有n-1次迭代行3-5的內(nèi)層for循環(huán)一共有m次迭代行4-5為內(nèi)層if指令，針對(duì)每個(gè)邊(u,v)依據(jù)目前的d[u]值調(diào)整d[v]的值:

O(1)行6-7的for回圈在求出(n-1)邊路徑之后再針對(duì)每個(gè)邊(u,v)依據(jù)目前的d[u]值調(diào)整d[v]的值，若有任何調(diào)整產(chǎn)生(也就是d[u]變小)，則表示給定的圖中一定有負(fù)循環(huán)存在。因此總時(shí)間復(fù)雜度為行2-5的外層for回圈n-1次迭代次數(shù)與行3-5的內(nèi)層for回圈m次迭代相乘得O(n

m)=O(|V|

|E|)29Bellman-Ford最短路徑算法

執(zhí)行范例30

Floyd-Warshall

最短路徑算法31Floyd-Warshall最短路徑算法介紹Floyd-Warshall算法與Dijkstra算法及Bellman-Ford算法不同，它可以求出全部節(jié)點(diǎn)配對(duì)的最短路徑，是一個(gè)全配對(duì)最短路徑(all-pairshortestpath)算法。Floyd-Warshall算法可以處理有負(fù)邊的圖，但是不能用以檢查有負(fù)循環(huán)的圖。也就是說，當(dāng)圖有負(fù)邊但是沒有負(fù)循環(huán)時(shí)，F(xiàn)loyd-Warshall算法仍然可以求出正確的最短路徑。32Floyd-Warshall最短路徑算法介紹(續(xù))Floyd-Warshall算法采用動(dòng)態(tài)規(guī)劃策略解決問題，利用一個(gè)n×n(n為節(jié)點(diǎn)總數(shù))的二維陣列d來記錄每一節(jié)點(diǎn)配對(duì)間的最短路徑成本或距離(distance)。在啟始(initial)狀況時(shí)，

d[i][j]=w[i][j]，foreachiandj。也就是節(jié)點(diǎn)i可以直接抵達(dá)節(jié)點(diǎn)j(也就是不經(jīng)過其他中間節(jié)點(diǎn))的距離。(w[i][j]=0，fori=j;w[i][j]=

,for(i,j)E;w[i][j]=theweightof(i,j)for(i,j)E)Floyd-Warshall算法執(zhí)行時(shí)會(huì)不斷的更新陣列d。在第k次更新陣列d時(shí)，表示d中所紀(jì)錄的最短路徑距離，其對(duì)應(yīng)的路徑是經(jīng)由編號(hào)小于或等于k的節(jié)點(diǎn)當(dāng)作中間節(jié)點(diǎn)所造成的。因此，當(dāng)?shù)趎次更新陣列d時(shí)，則表示d中所紀(jì)錄的最短路徑距離，其對(duì)應(yīng)的路徑是是可以經(jīng)由編號(hào)小於或等於k的節(jié)點(diǎn)(也就是所有節(jié)點(diǎn))當(dāng)作中間節(jié)點(diǎn)所造成的，這也就是算法所需要的最終最短路徑結(jié)果。33Floyd-Warshall最短路徑算法AlgorithmFloyd-Warshall最短路徑算法Input：G為一個(gè)加權(quán)圖有向(weighteddigraph)，G中各邊的加權(quán)值以w[x][y]表示，x及y為邊的二個(gè)頂點(diǎn)。

Output：G中的每一個(gè)節(jié)點(diǎn)配對(duì)的最短路徑距離d[x][y]，及