最短路徑學(xué)年論文(完整版)
【正文】 ,3,2}32（8）124{1,3,2,4}328（12）155{1,3,2,4}32812（12）找最短路線:逆向追蹤得最短距離為12,即從城市到城市的距離最短,即費(fèi)用最省。Dijkstra算法每次從V—S中取出具有最短路徑長度的頂點(diǎn)u，將u添加到S中，同時對短路徑進(jìn)行修改。為了求出賦權(quán)圖中任意兩結(jié)點(diǎn)之間的最短路徑,通常采用兩種方法。定義1若圖G=G(V,E)中各邊e都賦有一個實數(shù)W(e),稱為邊e的權(quán),則稱這種圖為賦權(quán)圖,記為G=G(V,E,W)。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時間、費(fèi)用、線路容量等。118 論文總結(jié)74 Floyd算法摘要：主要介紹最短路徑問題中的經(jīng)典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在實際生活中的運(yùn)用。11引言27117 附錄最短路徑算法的選擇與實現(xiàn)是通道路線設(shè)計的基礎(chǔ),最短路徑算法是計算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點(diǎn),很多網(wǎng)絡(luò)相關(guān)問題均可納入最短路徑問題的范疇之中。定義2若圖G=G(V,E)是賦權(quán)圖且,假設(shè)[i,j] 的權(quán)記為,若i與j之間沒有邊相連接，那么。一種方法是每次以一個結(jié)點(diǎn)為源點(diǎn),重復(fù)執(zhí)行Dijkstra算法n次。一旦S包含了所有V中頂點(diǎn)，那么最后記錄的最短路徑就是源到所有其他頂點(diǎn)之間的最短路徑長度。Dijkstra算法是貪心算法策略的一個典型例子。將添加u之前的S成為老S。i老S源xvu圖3 非最短路徑的特殊路徑 計算復(fù)雜性對于一個具有n個頂點(diǎn)和e條帶權(quán)邊的圖來說，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要的時間。Floyd算法只能求出兩點(diǎn)間最短路徑的長度，無法得到這條最短路徑，當(dāng)然，如果記錄了每步更新所經(jīng)過的中間結(jié)點(diǎn)，仍可通過回溯得到兩點(diǎn)間的最短路徑。我們可以從和中找到任何兩個端點(diǎn)間的最短徑長和最短路由，對應(yīng)著我們所建立的旅行線路模型中的任何兩景點(diǎn)間的最短路徑長度和路線。 其中Dijkstra算法中的例子，可以另對應(yīng)于標(biāo)號，鄰接矩陣為A，通過調(diào)用Matlab功能函數(shù)可迅速得出最優(yōu)路徑及相關(guān)途經(jīng)點(diǎn)。endvisited(1:n)=0。 [a,u]=min(vec)。 while t~=s,p=parent(t)。 r(i,j)=r(i,k) end end end k d r end8論文總結(jié)本文
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1