版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
迪杰斯特拉算法實(shí)現(xiàn)第九組11123529-羅凱耀11123575-王鳴迪杰斯特拉--算法思想按從某頂點(diǎn)到其它頂點(diǎn)的路徑長度遞增的方式,逐漸求到各頂點(diǎn)的最短路徑。設(shè)給定源點(diǎn)為Vs,S為已求得最短路徑的終點(diǎn)集,開始時(shí)令S={Vs}。當(dāng)求得第一條最短路徑(Vs,Vi)后,S為{Vs,Vi}。根據(jù)以下結(jié)論可求下一條最短路徑。設(shè)下一條最短路徑終點(diǎn)為Vj,則Vj只有:◆
源點(diǎn)到終點(diǎn)有直接的弧<Vs,Vj>;◆
從Vs出發(fā)到Vj的這條最短路徑所經(jīng)過的所有中間頂點(diǎn)必定在S中。即只有這條最短路徑的最后一條弧才是從S內(nèi)某個(gè)頂點(diǎn)連接到S外的頂點(diǎn)Vj。若定義一個(gè)數(shù)組dist[n],其每個(gè)dist[i]分量保存從Vs出發(fā)中間只經(jīng)過集合S中的頂點(diǎn)而到達(dá)Vi的所有路徑中長度最小的路徑長度值,則下一條最短路徑的終點(diǎn)Vj必定是不在S中且值最小的頂點(diǎn),即:dist[i]=Min{dist[k]|Vk∈V-S}利用上述公式就可以依次找出下一條最短路徑。迪杰斯特拉-算法思想源迪杰斯特拉算法
--數(shù)據(jù)組織源有n個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)數(shù)據(jù)源已確定結(jié)點(diǎn)集S待選結(jié)點(diǎn)集V-S結(jié)點(diǎn)臨時(shí)最短路徑長度結(jié)點(diǎn)臨時(shí)最短路徑迪杰斯特拉算法—步驟
①令S={Vs},用帶權(quán)的鄰接矩陣表示有向圖,對圖中每個(gè)頂點(diǎn)Vi按以下原則置初值:②
選擇一個(gè)頂點(diǎn)Vj,使得:
Distance[j]=Min{Distance[k]|Vk∈V-S}Vj就是求得的下一條最短路徑終點(diǎn),將Vj并入到S中,即S=S∪{Vj}。③對V-S中的每個(gè)頂點(diǎn)Vk,修改dist[k],方法是:若Distance[j]+Wjk<Distance[k],則修改為:Distance[k]=Distance[j]+Wjk(
Vk∈V-S)④重復(fù)②,③,直到S=V為止。Wsii≠s且<vs,vi>∈E,wsi為弧上的權(quán)值∞i≠s且<vs,vi>不屬于Edist[i]=0i=s迪杰斯特拉算法—實(shí)現(xiàn)voidDijkstra(MGraphg,intstart,intend){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<g.n;i++){dist[i]=g.edges[start][i];//dist數(shù)組初始化s[i]=0;if(g.edges[start][i]<INF) path[i]=start;else path[i]=-1;//path數(shù)組初始化}s[start]=1;//頂點(diǎn)start加入頂點(diǎn)集合s path[start]=0;for(i=0;i<g.n;i++)//選擇不在集合s中且具有最短路徑的頂點(diǎn){mindis=INF;for(j=0;j<g.n;j++){if(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}}s[u]=1;//將頂點(diǎn)u加入集合for(j=0;j<g.n;j++)//修改dist和path{if(s[j]==0){ if((g.edges[u][j]<INF)&&(dist[u]+g.edges[u][j]<dist[j])){dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}}}Dispath(g,dist,path,s,g.n,start,end);}已完成結(jié)點(diǎn)集S,本次最近點(diǎn)ABCDEF1{}DistancePath2DistancePath3DistancePath4DistancePath5(n-1)DistancePathEFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF運(yùn)算過程表鄰接矩陣圖數(shù)據(jù)源——鄰接矩陣已確定結(jié)點(diǎn)集S待選結(jié)點(diǎn)集V-S結(jié)點(diǎn)臨時(shí)最短路徑長度——Distance數(shù)組結(jié)點(diǎn)臨時(shí)最短路徑——Path數(shù)組Dijkstra算法--數(shù)據(jù)組織已完成結(jié)點(diǎn)集,本次最近點(diǎn)ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12DistancePath3DistancePath4DistancePath5(n-1)DistancePath運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF鄰接矩陣圖例:計(jì)算從A點(diǎn)出發(fā)的單源最短路徑已完成結(jié)點(diǎn)集,本次最近點(diǎn)ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12{A,C},FDistance020530¥12PathACAA-1C3DistancePath4DistancePath5(n-1)DistancePath運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF鄰接矩陣圖例:計(jì)算從A點(diǎn)出發(fā)的單源最短路徑已完成結(jié)點(diǎn)集,本次最近點(diǎn)ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12{A,C},FDistance020530¥12PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4DistancePath5(n-1)DistancePath運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF鄰接矩陣圖例:計(jì)算從A點(diǎn)出發(fā)的單源最短路徑已完成結(jié)點(diǎn)集,本次最近點(diǎn)ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12{A,C},FDistance020530¥12PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4{A,C,F,B},DDistance0205222812PathACAFBC5(n-1)DistancePath運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF鄰接矩陣圖例:計(jì)算從A點(diǎn)出發(fā)的單源最短路徑已完成結(jié)點(diǎn)集,本次最近點(diǎn)ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12{A,C},FDistance020530¥12PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4{A,C,F,B},DDistance0205222812PathACAFBC5(n-1){A,C,F,B,D},EDistance0205222812PathACAFBC運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF鄰接矩陣圖例:計(jì)算從A點(diǎn)出發(fā)的單源最短路徑最短路徑結(jié)點(diǎn)集ABCDEF{A,C,F,B,D,E}Distance0205222812PathACAFBC運(yùn)算結(jié)果Dijkstra算法—例子úúúúúúúú?ùêêêêêêêê?饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDE
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 彩鋼棚制作安裝合同
- 合同模板權(quán)威網(wǎng)址查詢
- 無人機(jī)安裝服務(wù)合同模板
- 旅店居住合同模板
- 加工后補(bǔ)合同模板
- 砂石機(jī)械合作合同模板
- 固定資料轉(zhuǎn)讓合同模板
- 加工毛巾合同模板
- 2024-2030年中國第三方電子支付行業(yè)市場發(fā)展分析及競爭格局與投資前景研究報(bào)告
- 2024-2030年中國竹活性炭市場營銷渠道分析及發(fā)展?jié)摿υu估報(bào)告
- 媽祖文化完整
- 30題留學(xué)顧問崗位常見面試問題含HR問題考察點(diǎn)及參考回答
- 初中體育籃球雙手胸前傳接球教案
- 鐵總建設(shè)201857號 中國鐵路總公司 關(guān)于做好高速鐵路開通達(dá)標(biāo)評定工作的通知
- GB/T 9128.1-2023鋼制管法蘭用金屬環(huán)墊第1部分:PN系列
- 機(jī)床數(shù)控技術(shù)PPT完整全套教學(xué)課件
- 第三單元名著導(dǎo)讀《朝花夕拾-二十四孝圖》課件(15張PPT) 部編版語文七年級上冊
- 招商接待流程
- 六年級一般疑問句練習(xí)
- 檢驗(yàn)科實(shí)驗(yàn)室生物安全培訓(xùn)計(jì)劃
- 心臟體格檢查.ppt
評論
0/150
提交評論