最短路徑問(wèn)題的算法分析及建模案例-文庫(kù)吧在線文庫(kù)
【正文】 .Key words: puter graph traffic road network The shortest path前言 最短路徑問(wèn)題是圖論以及運(yùn)籌學(xué)中的一個(gè)非常重要的問(wèn)題，在生產(chǎn)實(shí)踐，運(yùn)輸及工程建筑等方面有著十分廣泛的應(yīng)用。 簡(jiǎn)單圖定義：沒(méi)有環(huán)且沒(méi)有重邊的圖稱(chēng)之為簡(jiǎn)單圖。 途徑，跡，路定義：設(shè)圖G=（V,E），若它的某些頂點(diǎn)與邊可以排成一個(gè)非空的有限交錯(cuò)序列（，,...,）,這里該途徑中邊互不相同，則稱(chēng)為跡；如果頂點(diǎn)互不相同，則稱(chēng)之為路。某旅客要從杭州乘飛機(jī)前往奧地利的薩爾斯堡，因?yàn)樗ε鲁俗w機(jī)，因此要選擇一條航線，使得在空中飛行的時(shí)間盡可能的少。算法在所有頂點(diǎn)被賦予永久標(biāo)號(hào)時(shí)結(jié)束。（3） 如果重點(diǎn)v已經(jīng)標(biāo)號(hào)，則停止。上述Dijkstra算法的MATLAB代碼：w=[0 2 1 8 inf inf inf。w1=w(1,:)。z(i)=u。 FLOYD算法原理（1）FLOYD算法求路徑矩陣的方法：在建立距離矩陣的同時(shí)可建立路徑矩陣R。起始：選定帶權(quán)值的鄰接矩陣（1）賦值：對(duì)所有的，1。3,0,2,inf,inf。表示第頂點(diǎn)到其他各頂點(diǎn)的最短路徑的路長(zhǎng)之和，最后取最小的所對(duì)應(yīng)的頂點(diǎn)作為消防站的建立點(diǎn)。inf,inf,inf,4,0,。問(wèn)應(yīng)該把這個(gè)消防站設(shè)置在哪個(gè)區(qū)，才能使該消防站到最遠(yuǎn)的區(qū)的路徑最短。（2）向點(diǎn)查找得：，...。 end endendlv=inf。s(1)=1。inf 1 inf 5 0 3 inf 9。 Dijstre算法的建模應(yīng)用舉例某城市要在該城市所轄的8個(gè)區(qū)中的區(qū)建立一個(gè)取水點(diǎn)，如圖所示的是這8個(gè)區(qū)之間的分布以及相鄰各區(qū)的距離。Dijkstra算法是一個(gè)解最短路徑問(wèn)題的算法，這個(gè)算法不僅可以找到最短的（，v），路徑而且可以給出從到圖中所有節(jié)點(diǎn)的最短路徑，基本步驟如下：（1） 設(shè)=0，對(duì)所有節(jié)點(diǎn)來(lái)說(shuō)，設(shè)=，并且將標(biāo)號(hào)為0，→t，d為和w之間的權(quán)值（距離）。現(xiàn)找網(wǎng)絡(luò)中一條從指定頂點(diǎn)vi到另一個(gè)指定頂點(diǎn)vj的最短有向路徑。 有向途徑定義：設(shè)有一個(gè)有向圖G=（V,A），G中某些頂點(diǎn)與弧組成的非空有限序列（，...，）這里，...，V，A，且=（，），則稱(chēng)它為從到的有向途徑。圖2就是一個(gè)有向圖。圖1就是一個(gè)圖。 由于最短路徑問(wèn)題在各方面廣泛應(yīng)用，以及研究人員對(duì)最短路徑的深入研究，使得在最短路徑問(wèn)題中也產(chǎn)生了很多經(jīng)典的算法。在本課題中我將提出一些最短路徑問(wèn)題的算法以及各算法之間的比較，最后將這些算法再應(yīng)用于實(shí)際問(wèn)題的建模問(wèn)題中。 注釋?zhuān)簣D形的大小，位置，形狀是無(wú)關(guān)緊要的。 圖2 環(huán)定義：頭尾重合的弧稱(chēng)為環(huán)。類(lèi)似的可定義有向跡，有向路，有向閉途徑，有向閉跡，有向回路（圈）等。三 最短路徑算法研究 Dijkstra算法 D
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1