實驗6最短路徑問題

1、 HUNAN UNIVERSITY數(shù)據(jù)結(jié)構(gòu)實驗報告學生姓名 學生學號 專業(yè)班級 實驗6:最短路徑問題 背景乘汽車旅行的人總希望找出到目的地的盡可能短的行程。如果有一張地圖并在圖上標出每對十字路口之間的距離，如何找出這一最短行程？ 計算機網(wǎng)絡(luò)中的路由就是通過互聯(lián)的網(wǎng)絡(luò)把信息從源地址傳輸?shù)侥康牡刂返幕顒印榱烁咝б龑?dǎo)數(shù)據(jù)的傳輸，如何找出源和目的地址之間的最優(yōu)路徑？ 這些問題中的網(wǎng)絡(luò)（交通網(wǎng)，計算機通信網(wǎng)）可以使用一個帶權(quán)圖來建模，尋找最優(yōu)路的需求可轉(zhuǎn)換為帶權(quán)圖的最短路徑問題。最短路徑問題是圖論研究中的一個經(jīng)典算法問題， 旨在尋找圖（由結(jié)點和邊組成的）中兩結(jié)點之間的最短路徑。問題具體的形式包括： l

2、 確定起點的最短路徑問題，即已知起始結(jié)點，求最短路徑的問題。適合使用Dijkstra算法。l 確定終點的最短路徑問題，與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。l 確定起點終點的最短路徑問題，即已知起點和終點，求兩結(jié)點之間的最短路徑。l 全局最短路徑問題，求圖中所有的最短路徑。適合使用Floyd-Warshall算法。問題描述：若用有向網(wǎng)表示某地區(qū)的公路交通網(wǎng)，其中頂點表示該地區(qū)的一些主要場所，弧表示已有的公交線路，弧上的權(quán)表示票價。試設(shè)計一個交通咨詢系統(tǒng)，指導(dǎo)乘客以最少花費

3、從該地區(qū)中的某一場所到達另一場所?；疽?（1） 從文件中讀入有向網(wǎng)中頂點的數(shù)量和頂點間的票價的矩陣。（2） 以用戶指定的起點和終點，輸出從起點到終點的花費。 測試數(shù)據(jù)輸入（文件） 51 10 3 20 1 1 1 1 5 1 1 2 1 1 151 1 1 1 11 1 1 1 1 1 （用戶） 起點0 終點4 輸出18需求分析：1、本程序需要用矩陣來存儲圖的各種信息。概要設(shè)計抽象數(shù)據(jù)類型：為實現(xiàn)上述功能需建立一個二維數(shù)組和圖類。算法的基本思想：1、 圖的信息的讀?。憾x一個二維數(shù)組，將圖的信息讀入，并將兩邊距離為-1的邊轉(zhuǎn)換為一個較大的數(shù)（途中各點之間的距離）。2、 Dijkstra算法

4、：根據(jù)輸入的第一個結(jié)點首先找到（直接距離）該點最近的A，則這兩點之間的邊是必須的，然后比較通過A到其他點的距離l1和直接到其他點的距離l2。如果l1l2，則用l1的距離替換l2。重復(fù)上述操作n-1（n為結(jié)點數(shù)）次。得到的即為第一個結(jié)點到其他結(jié)點的最短距離。程序的流程： （1） 輸入模塊： 讀入圖的信息（用矩陣進行存儲）。（2） 處理模塊：Dijkstra算法。（3） 輸出模塊：將收入結(jié)點到其他點的最短距離輸出。 代碼:#include#define N 30using namespace std;int aNN; class Graph private: int ver; public: Gr

5、aph(int v)ver=v; void build(); void Dijkstra(int start,int end); void printf(int start); ;void Graph:build() /構(gòu)建圖 int temp,max=1000; for(int i=0;iver;i+) for(int j=0;jtemp; if(temp=-1) /-1表示兩點之間無直接聯(lián)系，將距離賦為500 aij=1000; else aij=temp; void Graph:Dijkstra(int start,int end) /最小路徑的算法 int distN,sN; int

6、i,j,min,pos; for(i=0;iver;i+) if(i=start) si=1; /標記邊是否被訪問 else si=0; for(i=0;iver;i+) disti=astarti; /該點到其他邊的距離 for(i=0;iver-1;i+) /共有n個頂點，故要重復(fù)n-1 min=500;pos=0; for(j=0;jver;j+) if(sj=0 & distjmin) min=distj; /找出最小邊,則該邊是最短路徑所必須的 pos=j; spos=1; for(j=0;jdistpos+aposj) /如過通過pos這條邊的距離小于原先的距離 distj=distpos+aposj; /改變距離 for(i=0;iver;i+) if(i!=start) /不會有起點到起點的路徑 coutstarti