實(shí)驗(yàn)6最短路徑問(wèn)題

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

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

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

4、：根據(jù)輸入的第一個(gè)結(jié)點(diǎn)首先找到（直接距離）該點(diǎn)最近的A，則這兩點(diǎn)之間的邊是必須的，然后比較通過(guò)A到其他點(diǎn)的距離l1和直接到其他點(diǎn)的距離l2。如果l1l2，則用l1的距離替換l2。重復(fù)上述操作n-1（n為結(jié)點(diǎn)數(shù)）次。得到的即為第一個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短距離。程序的流程： （1） 輸入模塊： 讀入圖的信息（用矩陣進(jìn)行存儲(chǔ)）。（2） 處理模塊：Dijkstra算法。（3） 輸出模塊：將收入結(jié)點(diǎn)到其他點(diǎn)的最短距離輸出。 代碼:#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表示兩點(diǎn)之間無(wú)直接聯(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; /標(biāo)記邊是否被訪問(wèn) else si=0; for(i=0;iver;i+) disti=astarti; /該點(diǎn)到其他邊的距離 for(i=0;iver-1;i+) /共有n個(gè)頂點(diǎ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) /如過(guò)通過(guò)pos這條邊的距離小于原先的距離 distj=distpos+aposj; /改變距離 for(i=0;iver;i+) if(i!=start) /不會(huì)有起點(diǎn)到起點(diǎn)的路徑 coutstarti