Dijkstra最短路徑的算法思想-南京大學(xué)課件

最短通路問題離散數(shù)學(xué)─圖論初步南京大學(xué)計算機科學(xué)與技術(shù)系最短通路問題離散數(shù)學(xué)─圖論初步內(nèi)容提要引言Dijkstra算法旅行商問題（TSP）內(nèi)容提要引言埃德斯數(shù)（Erd?snumber）PaulErd?s(1913-1996),Hungary,U.S.A.,IsraelErd?snumber

埃德斯數(shù)（Erd?snumber）PaulErd?s(帶權(quán)圖與最短通路問題帶權(quán)圖：三元組(V,E,W)，(V,E)是圖，W是從E到非負(fù)實數(shù)集的一個函數(shù)。W(e)表示邊e的權(quán)。一條通路上所有邊的權(quán)的和稱為該通路的長度。兩點之間長度最小的通路稱為兩點之間的最短通路，不一定是唯一的。單源點最短路問題給定帶權(quán)圖G(V,E,W)，并指定一個源點，確定該源點到圖中其它任一頂點的最短路（長度和路徑）。帶權(quán)圖與最短通路問題帶權(quán)圖：三元組(V,E,W)，(VDijkstra最短路徑的算法思想(1959)源點s到頂點v的最短路徑若為s…uv,則s…u是s到u的最短路徑。(n-1)條最短路徑按照其長度的非減次序求得，設(shè)它們的相應(yīng)端點分別為u1,…un-1，最短路徑長度記為d(s,ui)，i=1,…n-1.假設(shè)前i條最短路徑已知，第(i+1)條最短路徑長度：d(s,ui+1)=min{d(s,uj)+W(uj,ui+1)|j=1,…i}Dijkstra最短路徑的算法思想(1959)源點s到頂點v求最短路徑的Dijkstra算法輸入：連通帶權(quán)圖G，|VG|=n,指定頂點s

VG輸出：每個頂點v的標(biāo)注(L(v),u),其中：L(v)即從s到v的最短路徑長度（目前可得的）u是該路徑上v前一個頂點。求最短路徑的Dijkstra算法輸入：連通帶權(quán)圖G，|VG|求最短路的一個例子s77212412448353

4630bacdefgh求最短路的一個例子s772124124483534630b求最短路的一個例子s77212412448353

46301,c2,c8,c7,c4,cU1bacdefgh求最短路的一個例子s7721241244835346301s77212412448353

46301,c2,c8,c7,c4,cU2bacdefgh4,bS1s7721241244835346301,c2,c8,c7s77212412448353

46301,c2,c8,c7,c4,cU3bacdefgh4,bS23,e6,es7721241244835346301,c2,c8,c7s77212412448353

46301,c2,c8,c6,e4,cbacdefghU43,e9,hS3s7721241244835346301,c2,c8,c6s77212412448353

46301,c2,c8,c6,e4,cbacdefghU53,e9,hS46,ds7721241244835346301,c2,c8,c6求最短路的一個例子(續(xù))s77212312448353

46501266439求最短路的一個例子(續(xù))s7721231244835346求最短路的一個例子(續(xù))s77212512448353

4630s77212312448353

465012664126433969求最短路的一個例子(續(xù))s7721251244835346Dijkstra算法的描述1．初始化：i=0,S0={s},L(s)=0,對其它一切v

VG,將L(v)置為

。

若n=1，結(jié)束。2．

v

Si'=VG-Si,比較L(v)和L(ui)+W(ui,v)的值(ui

Si)

如果L(ui)+W(ui,v)<L(v),則將v的標(biāo)注更新為(L(ui)+W(ui,v),ui)，

即：L(v)=min{L(v),minu

Si{L(u)+W(u,v)}}3.對所有Si'中的頂點，找出具有最小L(v)的頂點v,作為ui+14．Si+1=Si?{ui+1}5.i=i+1;若i=n-1,終止。否則：轉(zhuǎn)到第2步。

Dijkstra算法的描述1．初始化：i=0,S0={s}Dijkstra算法的分析可終止性計數(shù)控制正確性

需證明當(dāng)算法終止時L(v)=d(s,v)對一切v成立。由標(biāo)記中的諸ui確定的路徑是一條最短路徑

(這里d(s,v)是s到v的最短路徑長度，即距離。)復(fù)雜性O(shè)(n2)Dijkstra算法的分析可終止性旅行商問題

(TravellingSalesmanProblem,TSP)n個城市間均有道路，但距離不等，旅行商從某地出發(fā)，走過其它n-1城市各一次，最后回到原地，如何選擇最短路線？數(shù)學(xué)模型：無向帶權(quán)圖G：頂點對應(yīng)于城市，邊對應(yīng)于城市之間的道路，道路長度用相應(yīng)邊的權(quán)表示。問題的解：權(quán)最小的哈密爾頓回路。G是帶權(quán)完全圖，總共有(n-1)!/2條哈密爾頓回路。因此，問題是如何從這(n-1)!/2條中找出最短的一條。(含25個頂點的完全圖中不同的哈密爾頓回路有約3.11023條，若機械地檢查，每秒處理109條，需1千萬年。)旅行商問題

(TravellingSalesmanPro旅行商問題一個貨郎（銷售員）生活在城市a，假定訪問的城市是d,b,c，然后回到a，求完成這次訪問的最短路徑的距離.1814bcad1110127旅行商問題一個貨郎（銷售員）生活在城市a，假定訪問的城市是d旅行商問題解：列出哈密爾頓回路,并求其距離：（1）（abcda）=（12+7+11+18）=48（2）（acbda）=（14+7+10+18）=49（3）（abdca）=（12+10+11+14）=471814bcad1110127旅行商問題解：列出哈密爾頓回路,并求其距離：1814bca哈密爾頓回路（路徑）的最短路徑問題！下面介紹一種最鄰近算法：（1）選擇任一頂點作為始點，找出離始點距離最小的頂點，形成一條邊的初始路徑；（2）設(shè)u是最新加到這條路徑上的頂點，從不在這條路徑上的所有頂點中選擇一個與u距離最小的頂點,把連接u與此結(jié)點的邊加入路徑中；重復(fù)執(zhí)行直到G中的各頂點均含在這條路徑中。

旅行商問題哈密爾頓回路（路徑）的最短路徑問題！旅行商問題旅行商問題

（3）把始點到最后加入的頂點的邊放入路徑中得到一條哈密爾頓回路，并為近似最短的哈密爾頓回路.1814bcad1110127旅行商問題（3）把始點到最后加入的頂點的邊放入路徑中得到一旅行商問題(TSP)的研究進展（在最壞情況下）時間復(fù)