最短路徑學年論文-資料下載頁
2025-06-26 05:23本頁面
【正文】 就是要經(jīng)點2轉(zhuǎn)接；再看，此時已經(jīng)到達目的節(jié)點，所以路由是。5 Dijkstra算法和Floyd算法在求最短路徑的異同相同：① 是按路徑長度遞增的思路進行查找最短路徑。 ② 都需要借助帶權(quán)領(lǐng)接矩陣； ③ 都引進了輔助數(shù)組； ④ Floyd法的替代算法是n次調(diào)用Dijkstra法（n為圖G中結(jié)點數(shù)目）。 相異： ① Dijkstra算法是從一點出發(fā)到其余路徑的最短路徑，而Floyd算法是找圖中所有頂點間的最短路徑； ② Dijkstra算法是找到最短后再嘗試利用該最短輔助找其余最短的；而Floyd算法是在插入第i1個頂點的基礎(chǔ)上比較插入第i個后和之前的最短； ③ 路徑長度遞增不一樣：Dijkstra算法增的路徑是比較出最短的增，而Floyd算法增的路徑是按編號遞增； ⑤ Dijkstra算法從源點出發(fā)，而弗法可以從任意點出發(fā)； ⑤ 結(jié)果不同，Dijkstra算法找到的是從源點到其余頂點的最短路徑；Floyd算法則可以求任兩點之間的最短路徑。6 利用計算機程序模擬算法對于圖G來說，如果G中的結(jié)點個數(shù)較少，可以通過逐步迭代或者通過以上的列表形式算出不同點之間的最短路徑，但相對于結(jié)點數(shù)目較多的圖而言，顯得力不從心，也大大增加了計算過程中的失誤率。這個時候，我們就迫切希望尋求算學工具來解決人工的局限性。為此引入Matlab來簡化求解步驟，通過輸入鄰接矩陣和始末點來快速計算最短路徑的值，并導出途經(jīng)各結(jié)點。 其中Dijkstra算法中的例子，可以另對應于標號，鄰接矩陣為A，通過調(diào)用Matlab功能函數(shù)可迅速得出最優(yōu)路徑及相關(guān)途經(jīng)點。程序見附錄。7 附錄Dijkstra算法：function [d,path]=dijkstra(W,s,t)[n,m]=size(W)。ix=(W==0)。W(ix)=inf。if n~=m,error(39。Square W required39。)。endvisited(1:n)=0。 dist(1:n)=inf。parent(1:n)=0。dist(s)=0。d=inf。for i=1:(n1), ix=(visited==0)。vec(1:n)=inf。vec(ix)=dist(ix)。 [a,u]=min(vec)。visited(u)=1。 for v=1:n,if (W(u,v)+dist(u)dist(v)), dist(v)=dist(u)+W(u,v)。parent(v)=u。 end。end。endif parent(t)~=0,path=t。d=dist(t)。 while t~=s,p=parent(t)。path=[p path]。t=p。end。endFloyd算法：function [d,r]=floyd(a) n=size(a,1)。 d=a。 for i=1:n for j=1:n r(i,j)=j。 end end r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j)。 r(i,j)=r(i,k) end end end k d r end8論文總結(jié)本文將最短路徑理論應用到實際生活中，具有很重要的意義。將實際生活中出現(xiàn)的問題進行優(yōu)化解決。同時也凸顯出學習和應用最短路問題原理的重要性。另外，最短路問題在城市道路建設(shè)、物資供應站選址等問題上也有很重要的作用，分析和研究最短路問題將趨于熱門化。9 參考文獻[1] 計算機算法設(shè)計與分析 王曉東著 電子工業(yè)出版社[2] 離散數(shù)學 方世昌著 西安電子科技大學出版社[3] Matlab程序設(shè)計教程 劉衛(wèi)國著 中國水利水電出版社[4] 數(shù)學建模簡明教程 袁震東、蔣魯敏、束金龍著 華東師范大學出版社[5] 數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴蔚敏、吳偉民著 清華大學出版社 19
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1