最短路徑問(wèn)題的算法分析及建模案例-免費(fèi)閱讀
【正文】 [d,r]=floyd(w)S=max(d’)%求矩陣各列的最大值s=min(S) Dijkstra算法與Floyd算法的比較。，由于=那么應(yīng)該將消防站設(shè)置在處。：表示到之間的距離。v=i。k=1。inf inf 9 2 inf 4 0 3。先寫出帶權(quán)鄰接矩陣：W=因?yàn)镚是無(wú)向圖，所以W是對(duì)稱矩陣。如果標(biāo)號(hào)被修改了說(shuō)明在當(dāng)前得到的到w的最優(yōu)路徑上t和w相鄰，用記錄下來(lái)在所有中選擇一個(gè)最小的即，w未標(biāo)號(hào)。算法開(kāi)始時(shí)，只有頂點(diǎn)被賦予永久標(biāo)號(hào)=0，其他頂點(diǎn)賦予臨時(shí)標(biāo)號(hào)。當(dāng)G時(shí)簡(jiǎn)單有向圖時(shí)，從到的一條有向途徑可簡(jiǎn)記為（，...,）。 簡(jiǎn)單有向圖定義：沒(méi)有環(huán)和重弧的有向圖稱為簡(jiǎn)單有向圖。若={,}則稱連接和；點(diǎn)和稱為的頂點(diǎn)，和是鄰接的頂點(diǎn)；如果兩條邊有公共的一個(gè)頂點(diǎn)，則稱這兩邊是鄰接的。 關(guān)鍵詞：計(jì)算機(jī) 圖論 交通道路網(wǎng) 最短路徑A. In this paper, Computer developing rapidly in recent years, graph theory research also have been greatly developed, and the shortest path problem is a typical problem in graph theory, it has been applied in geographical information science, puter science, and many other fields. And in the transportation network of the shortest route between two cities in is a typical example of the shortest path problem.Due to the shortest path problem is widely used in various aspects, and the researchers on the indepth study of the shortest path, make而在交通路網(wǎng)中兩個(gè)城市之間的最短行車路線就是最短路徑問(wèn)題的一個(gè)典型例子。一 網(wǎng)絡(luò)最短路徑問(wèn)題的基礎(chǔ)知識(shí) 圖1 圖 圖G是一個(gè)（無(wú)向）圖，其中有序二元組（V,E），V=｛，,...｝是頂點(diǎn)集，E=｛｝是集，是一個(gè)無(wú)序二元組{，}它表示該邊連接的是頂點(diǎn)。稱為連向的弧，為的出弧，的入??；稱為的得尾，稱為aij的頭；稱為的前繼，稱為的后繼。如果圖G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖。設(shè)G=（V,A,w）是一個(gè)有向網(wǎng)絡(luò)，p為G中一條有向路，
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1