最短路徑問題的算法分析及建模案例-免費閱讀
【正文】 [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=因為G是無向圖，所以W是對稱矩陣。如果標號被修改了說明在當前得到的到w的最優(yōu)路徑上t和w相鄰，用記錄下來在所有中選擇一個最小的即，w未標號。算法開始時，只有頂點被賦予永久標號=0，其他頂點賦予臨時標號。當G時簡單有向圖時，從到的一條有向途徑可簡記為（，...,）。 簡單有向圖定義：沒有環(huán)和重弧的有向圖稱為簡單有向圖。若={,}則稱連接和；點和稱為的頂點，和是鄰接的頂點；如果兩條邊有公共的一個頂點，則稱這兩邊是鄰接的。 關(guān)鍵詞：計算機 圖論 交通道路網(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)中兩個城市之間的最短行車路線就是最短路徑問題的一個典型例子。一 網(wǎng)絡(luò)最短路徑問題的基礎(chǔ)知識 圖1 圖 圖G是一個（無向）圖，其中有序二元組（V,E），V=｛，,...｝是頂點集，E=｛｝是集，是一個無序二元組{，}它表示該邊連接的是頂點。稱為連向的弧，為的出弧，的入??；稱為的得尾，稱為aij的頭；稱為的前繼，稱為的后繼。如果圖G中任何兩個頂點都是連通的，則稱G是連通圖。設(shè)G=（V,A,w）是一個有向網(wǎng)絡(luò)，p為G中一條有向路，
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1