




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、最短路徑問(wèn)題,Mathematica Modeling,參考書(shū): 1.傅鸝 龔劬 劉瓊蓀 何中市 數(shù)學(xué)實(shí)驗(yàn)科學(xué)出版社 2.張紹民 李淑華 數(shù)據(jù)結(jié)構(gòu)教程C語(yǔ)言版中國(guó)電力出版社,主要內(nèi)容,Floyd算法,Dijkstra算法,兩個(gè)例子的求解,引例2:最廉價(jià)航費(fèi)表的制定,引例1:最短運(yùn)輸路線問(wèn)題,3,如圖的交通網(wǎng)絡(luò),每條弧上的數(shù)字代表車(chē)輛在該路段行駛所需的時(shí)間,有向邊表示單行道,無(wú)向邊表示可雙向行駛。若有一批貨物要從1號(hào)頂點(diǎn)運(yùn)往11號(hào)頂點(diǎn),問(wèn)運(yùn)貨車(chē)應(yīng)沿哪條線路行駛,才能最快地到達(dá)目的地?,引例1:最短運(yùn)輸路線問(wèn)題,4,某公司在六個(gè)城市C1,C2,C3,C4,C5,C6都有分公司,公司成員經(jīng)常往來(lái)于它
2、們之間,已知從Ci到Cj的直達(dá)航班票價(jià)由下述矩陣的第i行,第j列元素給出(表示無(wú)直達(dá)航班),該公司想算出一張任意兩個(gè)城市之間的最廉價(jià)路線航費(fèi)表。,引例2:最廉價(jià)航費(fèi)表的制定,5,最短路徑問(wèn)題,定義:設(shè)P(u,v)是加權(quán)圖G中從u到v的路徑,則該路徑上的邊權(quán)之和稱(chēng)為該路徑的權(quán),記為w(P). 從u到v的路徑中權(quán)最小者 P*(u,v)稱(chēng)為u到v的最短路徑.,最短路徑算法,Dijkstra算法 使用范圍: 尋求從一固定頂點(diǎn)到其余各點(diǎn)的最短路徑; 有向圖、無(wú)向圖和混合圖; 權(quán)非負(fù). 算法思路: 采用標(biāo)號(hào)作業(yè)法,每次迭代產(chǎn)生一個(gè)永久標(biāo)號(hào), 從而生長(zhǎng)一顆以v0為根的最短路樹(shù),在這顆樹(shù)上每個(gè)頂點(diǎn)與根節(jié)點(diǎn)之間
3、的路徑皆為最短路徑.,Dijkstra算法算法步驟,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), 即 l(v)l(u)+w(u,v),f(v)u; 重復(fù)步驟2), 直到所有頂點(diǎn)都在S中為止.,MATLAB程序(Dijkstra算法),function min,pat
4、h=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, end s(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; k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end, end if ins
5、=0 v=i; if klabel(v) k=label(v); v1=v; end, end, end s(length(s)+1)=v1; u=v1; end,min=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,最短路徑算法,Dijkstra算法程序的使用說(shuō)明: 調(diào)用格式為 min,path=dijkstra(w,start,terminal),
6、其中輸入變量w為所求圖的帶權(quán)鄰接矩陣,start, terminal分別為路徑的起點(diǎn)和終點(diǎn)的號(hào)碼。返回start到terminal的最短路徑path及其長(zhǎng)度min. 注意:頂點(diǎn)的編號(hào)從1開(kāi)始連續(xù)編號(hào)。,最短路徑算法,Floyd算法 使用范圍: 求每對(duì)頂點(diǎn)的最短路徑; 有向圖、無(wú)向圖和混合圖; 算法思想: 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出n個(gè)矩陣D(1), D(2), , D(n), D(n)是圖的距離矩陣, 同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑.,Floyd算法算法步驟,d(i,j) : i到j(luò)的距離; path(i,j): i到j(luò)的路徑上i的后繼點(diǎn); 輸入帶權(quán)鄰
7、接矩陣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+1 3)重復(fù)2)直到k=n+1,MATLAB程序(Floyd算法),function D,path,min1,path1=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n if D(
8、i,j)=inf path(i,j)=j; end, end, end for 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,end,if nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=te
9、rminal; path1=m; end,13,最短路徑算法,Floyd算法程序的使用說(shuō)明: 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.,14,edge= 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
10、,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; end for i=1:size(edge,2) weight(edge(1, i), edge(2, i)=edge(3, i); end dis, path=dijkstra(weight, 1, 11),引例1的Matlab求解,15,運(yùn)行上頁(yè)程序輸出: dis = 21 pa
11、th = 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 20 10 0
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 高一學(xué)生手冊(cè)考試試題及答案
- 一年級(jí)英語(yǔ)教學(xué)課件
- 甘肅特崗教師招聘考試真題2024
- 尿毒癥甲狀腺旁腺手術(shù)護(hù)理
- 學(xué)校心理健康教育知識(shí)講座
- 保定望都縣中醫(yī)醫(yī)院招聘筆試真題2024
- 冬季安全行車(chē)知識(shí)考試試題及答案
- 漢中市第二人民醫(yī)院招聘考試真題2024
- 2024年保定高陽(yáng)縣選聘教師考試真題
- 指數(shù)與對(duì)數(shù)函數(shù)課件
- 行政管理過(guò)程中道德與法律的關(guān)系試題及答案
- 2024-2025學(xué)年廣東省深圳市高一數(shù)學(xué)下學(xué)期7月期末考試(附答案)
- 2025-2030年中國(guó)核子及核輻射測(cè)量?jī)x器行業(yè)競(jìng)爭(zhēng)格局及發(fā)展趨勢(shì)分析報(bào)告
- 2025物業(yè)社區(qū)文化建設(shè)方案物業(yè)社區(qū)文化活動(dòng)方案2
- 高端寫(xiě)字樓安全管理
- 大學(xué)英語(yǔ)四六級(jí)詞匯表
- 2025年中考?xì)v史開(kāi)卷考查范圍重大考點(diǎn)全突破(完整版)
- AI基礎(chǔ)知識(shí)入門(mén)
- 2025年甘肅蘭州新區(qū)城投地產(chǎn)置業(yè)有限公司招聘筆試參考題庫(kù)附帶答案詳解
- 職稱(chēng)評(píng)審申報(bào)培訓(xùn)
- 中國(guó)硫氰酸紅霉素市場(chǎng)供需現(xiàn)狀及投資戰(zhàn)略研究報(bào)告
評(píng)論
0/150
提交評(píng)論