最短路徑算法課件

1、最短路徑問題Mathematica Modeling 參考書：1.傅鸝 龔劬 劉瓊蓀 何中市 數(shù)學(xué)實(shí)驗(yàn)科學(xué)出版社2.張紹民 李淑華 數(shù)據(jù)結(jié)構(gòu)教程C語言版中國電力出版社主講：重慶大學(xué) 龔 劬主要內(nèi)容Floyd算法Dijkstra算法兩個(gè)例子的求解引例2：最廉價(jià)航費(fèi)表的制定引例1：最短運(yùn)輸路線問題3如圖的交通網(wǎng)絡(luò)，每條弧上的數(shù)字代表車輛在該路段行駛所需的時(shí)間，有向邊表示單行道，無向邊表示可雙向行駛。若有一批貨物要從1號(hào)頂點(diǎn)運(yùn)往11號(hào)頂點(diǎn)，問運(yùn)貨車應(yīng)沿哪條線路行駛，才能最快地到達(dá)目的地？ 引例1：最短運(yùn)輸路線問題 102374116598135122106158879932274 某公司在六個(gè)城市C

2、1,C2,C3,C4,C5,C6都有分公司，公司成員經(jīng)常往來于它們之間，已知從Ci到Cj的直達(dá)航班票價(jià)由下述矩陣的第i行，第j列元素給出（表示無直達(dá)航班），該公司想算出一張任意兩個(gè)城市之間的最廉價(jià)路線航費(fèi)表。 引例2：最廉價(jià)航費(fèi)表的制定 5最短路徑問題定義：設(shè)P(u,v)是加權(quán)圖G中從u到v的路徑,則該路徑上的邊權(quán)之和稱為該路徑的權(quán),記為w(P). 從u到v的路徑中權(quán)最小者 P*(u,v)稱為u到v的最短路徑.10237411659813512210615887993227最短路徑算法Dijkstra算法使用范圍:尋求從一固定頂點(diǎn)到其余各點(diǎn)的最短路徑;有向圖、無向圖和混合圖;權(quán)非負(fù).算法思路：

3、 采用標(biāo)號(hào)作業(yè)法,每次迭代產(chǎn)生一個(gè)永久標(biāo)號(hào), 從而生長(zhǎng)一顆以v0為根的最短路樹,在這顆樹上每個(gè)頂點(diǎn)與根節(jié)點(diǎn)之間的路徑皆為最短路徑.10237411659813512210615887993227Dijkstra算法算法步驟S: 具有永久標(biāo)號(hào)的頂點(diǎn)集;l(v): v的標(biāo)記; f(v):v的父頂點(diǎn),用以確定最短路徑; 輸入加權(quán)圖的帶權(quán)鄰接矩陣w=w(vi,vj)nxm.初始化 令l(v0)=0,S=; vv0 ,l(v)=;更新l(v), f(v) 尋找不在S中的頂點(diǎn)u,使l(u)為最小.把u加入到S中,然后對(duì)所有不在S中的頂點(diǎn)v,如l(v)l(u)+w(u,v),則更新l(v),f(v), 即

4、l(v)l(u)+w(u,v),f(v)u;重復(fù)步驟2), 直到所有頂點(diǎn)都在S中為止.MATLAB程序（Dijkstra算法）function min,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;for i=1:n if i=start label(i)=inf;end, ends(1)=start; u=start;while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,v); f(v)=u; end, end, end v1=0;

5、k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end, end if ins=0 v=i; if klabel(v) k=label(v); v1=v; end, end, end s(length(s)+1)=v1; u=v1;endmin=label(terminal); path(1)=terminal;i=1; while path(i)=start path(i+1)=f(path(i); i=i+1 ;end path(i)=start;L=length(path);path=path(L:-1:1);9最短路

6、徑算法Dijkstra算法程序的使用說明： 調(diào)用格式為 min,path=dijkstra(w,start,terminal), 其中輸入變量w為所求圖的帶權(quán)鄰接矩陣，start, terminal分別為路徑的起點(diǎn)和終點(diǎn)的號(hào)碼。返回start到terminal的最短路徑path及其長(zhǎng)度min.注意：頂點(diǎn)的編號(hào)從1開始連續(xù)編號(hào)。最短路徑算法Floyd算法使用范圍:求每對(duì)頂點(diǎn)的最短路徑;有向圖、無向圖和混合圖;算法思想: 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出n個(gè)矩陣D(1), D(2), , D(n), D(n)是圖的距離矩陣, 同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑.10

7、237411659813512210615887993227Floyd算法算法步驟 d(i,j) : i到j(luò)的距離; path(i,j): i到j(luò)的路徑上i的后繼點(diǎn); 輸入帶權(quán)鄰接矩陣a(i,j).1）賦初值 對(duì)所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2）更新d(i,j) , path(i,j) 對(duì)所有i,j, 若d(i,k)+d(k,j)d(i,j),則 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+13）重復(fù)2)直到k=n+1MATLAB程序（Floyd算法）function D,path,min1,path

8、1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,endif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path

9、(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end 13最短路徑算法Floyd算法程序的使用說明：1. D, path=floyd(a), 返回矩陣D, path 。其中a是所求圖的帶權(quán)鄰接矩陣，D(i,j)表示i到j(luò)的最短距離; path(i,j)表示i與j之間的最短路徑上頂點(diǎn)i的后繼點(diǎn).2. D, path, min1, path1= floyd(a,i,j) 返回矩陣D, path; 并返回i與j之間的最短距離min1和最短路徑path1.14e

10、dge= 2,3,1,3,3,5,4, 4,1,7,6,6,5, 5,11, 1,8,6,9,10,8,9, 9,10;. 3,4,2,7,5,3,5,11,7,6,7,5,6,11, 5, 8,1,9,5,11,9,8,10,9;. 3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7, 2, 9,9, 2, 2;n=11; weight=inf*ones(n, n);for i=1:n weight(i, i)=0;endfor i=1:size(edge,2)weight(edge(1, i), edge(2, i)=edge(3, i);enddis, pa

11、th=dijkstra(weight, 1, 11)引例1的Matlab求解1023741165981351221061588799322715運(yùn)行上頁程序輸出：dis = 21path = 1 8 9 10 11 因此頂點(diǎn)1到頂點(diǎn)11的最短路徑為18 9 10 11, 其長(zhǎng)度為21。引例1的求解16建立腳本m文件如下：a= 0,50,inf,40,25,10;50,0,15,20,inf,25;inf,15,0,10,20,inf;40,20,10,0,10,25;25,inf,20,10,0,55;10,25,inf,25,55,0;D, path=floyd(a)運(yùn)行便可輸出結(jié)果。引例2的Matlab求解運(yùn)行輸出結(jié)果： D = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30