最短路徑學(xué)年論文-閱讀頁
2025-07-11 05:23本頁面
【正文】 其中一個結(jié)點(diǎn)為跳板，如果以該結(jié)點(diǎn)為跳板后兩結(jié)點(diǎn)間路徑縮短，則更新這兩結(jié)點(diǎn)間的路徑。若用Dijkstra算法計算任意兩點(diǎn)間的最短路徑，需要執(zhí)行n次，且圖中含有負(fù)權(quán)值時不能用Dijkstra算法。 Floyd算法步驟 對于圖G，如果表示i和j之間的可實(shí)現(xiàn)的距離，那么表示端i和j之間的最短距離當(dāng)且僅當(dāng)對于任意的i, j, k，有。其步驟如下：：置 其中 和 其中 ：已得和陣，求和陣中的元素如下 ：，重復(fù)；，終止。最后算得和，就得到了最短徑長和轉(zhuǎn)接路由。那么計算結(jié)果如下： 經(jīng)過7輪迭代，我們得到了最終的W和R陣，分別包含了徑長信息和路由信息。 若要求旅游點(diǎn)3到點(diǎn)1的最短路徑，則可以從中找到對應(yīng)的最小值為18，從中找到，就是要經(jīng)點(diǎn)2轉(zhuǎn)接；再看，此時已經(jīng)到達(dá)目的節(jié)點(diǎn)，所以路由是。 ② 都需要借助帶權(quán)領(lǐng)接矩陣； ③ 都引進(jìn)了輔助數(shù)組； ④ Floyd法的替代算法是n次調(diào)用Dijkstra法（n為圖G中結(jié)點(diǎn)數(shù)目）。6 利用計算機(jī)程序模擬算法對于圖G來說，如果G中的結(jié)點(diǎn)個數(shù)較少，可以通過逐步迭代或者通過以上的列表形式算出不同點(diǎn)之間的最短路徑，但相對于結(jié)點(diǎn)數(shù)目較多的圖而言，顯得力不從心，也大大增加了計算過程中的失誤率。為此引入Matlab來簡化求解步驟，通過輸入鄰接矩陣和始末點(diǎn)來快速計算最短路徑的值，并導(dǎo)出途經(jīng)各結(jié)點(diǎn)。程序見附錄。ix=(W==0)。if n~=m,error(39。)。 dist(1:n)=inf。dist(s)=0。for i=1:(n1), ix=(visited==0)。vec(ix)=dist(ix)。visited(u)=1。parent(v)=u。end。d=dist(t)。path=[p path]。end。 d=a。 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)。將實(shí)際生活中出現(xiàn)的問題進(jìn)行優(yōu)化解決。另外，最短路問題在城市道路建設(shè)、物資供應(yīng)站選址等問題上也有很重要的作用，分析和研究最短路問題將趨于熱
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1