實(shí)驗(yàn)報(bào)告6-最短路徑問題

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)書HUNAN UNIVERSITY課程實(shí)習(xí)報(bào)告題目最短路徑問題學(xué)生姓名 學(xué)生學(xué)號(hào) 專業(yè)年級(jí) 指導(dǎo)老師 完成日期 1、 需求分析本實(shí)驗(yàn)是求最短路徑的問題，從文件中讀入有向網(wǎng)中頂點(diǎn)的數(shù)量和頂點(diǎn)間的票價(jià)的矩陣，以用戶指定的起點(diǎn)，在文件中輸出到其余各頂點(diǎn)的最短路徑及花費(fèi)。（1） 輸入：輸入的形式：（文件） 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：0輸入值的范圍：文件輸入中，頂點(diǎn)數(shù)和矩陣中頂點(diǎn)間的票價(jià)均為整型int，用戶輸入中，起點(diǎn)數(shù)為整型int。（2） 輸

2、出的形式：（文件）源點(diǎn)0到頂點(diǎn)1的最小花費(fèi)為:5路徑為：0>2>1源點(diǎn)0到頂點(diǎn)2的最小花費(fèi)為:3路徑為：0>2源點(diǎn)0到頂點(diǎn)3的最小花費(fèi)為:10路徑為：0>2>1>3源點(diǎn)0到頂點(diǎn)4的最小花費(fèi)為:18路徑為：0>2>4（3） 程序所達(dá)到的功能：在文件中給出有向網(wǎng)的頂點(diǎn)個(gè)數(shù)和頂點(diǎn)間的票價(jià)的矩陣，以用戶指定的起點(diǎn)，在文件中輸出起點(diǎn)到其余各頂點(diǎn)的最短路徑及花費(fèi)。（4）測(cè)試數(shù)據(jù)： a.輸入：（文件） 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用戶） 輸

3、入起點(diǎn)：0 輸出：（文件） 源點(diǎn)0到頂點(diǎn)1的最小花費(fèi)為:5 路徑為：0>2>1 源點(diǎn)0到頂點(diǎn)2的最小花費(fèi)為:3 路徑為：0>2 源點(diǎn)0到頂點(diǎn)3的最小花費(fèi)為:10 路徑為：0>2>1>3 源點(diǎn)0到頂點(diǎn)4的最小花費(fèi)為:18 路徑為：0>2>4 b.輸入：（文件） 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：2 輸出：（文件） 源點(diǎn)2到頂點(diǎn)0：沒有連通路徑 源點(diǎn)2到頂點(diǎn)1的最小花費(fèi)為:2 路徑為：2>1 源點(diǎn)2到頂點(diǎn)3的最小

4、花費(fèi)為:7 路徑為：2>1>3 源點(diǎn)2到頂點(diǎn)4的最小花費(fèi)為:15 路徑為：2>4 c.輸入：（文件） 6 18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用戶） 輸入起點(diǎn)：5 輸出：（文件） 源點(diǎn)5到頂點(diǎn)0的最小花費(fèi)為:21 路徑為：5>1>3>4>0 源點(diǎn)5到頂點(diǎn)1的最小花費(fèi)為:8 路徑為：5>1 源點(diǎn)5到頂點(diǎn)2的最小花費(fèi)為:12 路徑為：5>2 源點(diǎn)5到頂點(diǎn)3的最小花費(fèi)為:13 路徑為：

5、5>1>3 源點(diǎn)5到頂點(diǎn)4的最小花費(fèi)為:19 路徑為：5>1>3>4 d.輸入：（文件） 6 18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用戶） 輸入起點(diǎn)：3 輸出：（文件） 源點(diǎn)3到頂點(diǎn)0的最小花費(fèi)為:8 路徑為：3>4>0 源點(diǎn)3到頂點(diǎn)1的最小花費(fèi)為:11 路徑為：3>5>1 源點(diǎn)3到頂點(diǎn)2的最小花費(fèi)為:11 路徑為：3>4>0>2 源點(diǎn)3到頂點(diǎn)4的最小花費(fèi)為:6

6、路徑為：3>4 源點(diǎn)3到頂點(diǎn)5的最小花費(fèi)為:3 路徑為：3>5 e.輸入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：1 輸出：（文件） 源點(diǎn)1到頂點(diǎn)0：沒有連通路徑 源點(diǎn)1到頂點(diǎn)2：沒有連通路徑 f.輸入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：3 輸出：（文件） 源點(diǎn)3到頂點(diǎn)0的最小花費(fèi)為:-572562307 路徑為：3>1>0 源點(diǎn)3到頂點(diǎn)1的最小花費(fèi)為:-572662307 路徑為：3>1 源點(diǎn)3到頂點(diǎn)2的最小花費(fèi)為:-572662307 路徑為：3>22、

7、 概要設(shè)計(jì)（1） 所有抽象數(shù)據(jù)類型的定義：const int MaxNum=100000;/利用鄰接矩陣存儲(chǔ)圖：class Graphprivate:int *Adj;/保存鄰接矩陣的一維數(shù)組j和k之間權(quán)值存儲(chǔ)在Adjj*Num+k中int Num;public:Graph();Graph();void Floyd(int start);（2） 算法的基本思想：采用鄰接矩陣為圖的存儲(chǔ)結(jié)構(gòu)，保存鄰接矩陣的一維數(shù)組j和k之間權(quán)值存儲(chǔ)Adjj*Num+k中，以用戶指定的起點(diǎn)，進(jìn)行弗洛伊德算法，先初始化最短路徑，對(duì)角線元素設(shè)置為0，其他元素設(shè)置為邊的權(quán)值，沒有有向邊設(shè)置為MaxNum，依次插入中間點(diǎn)k

8、，判斷是否檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，若不成立則路徑不改變，若成立則更新最短路徑，設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，直至循環(huán)結(jié)束，更新后的最短路徑入棧，在文件中輸出到其余各頂點(diǎn)的最短路徑及花費(fèi)。（3） 主程序的流程以及各程序程序由三個(gè)模塊組成：輸入模塊：讀取文件中的頂點(diǎn)個(gè)數(shù)及各邊權(quán)值，將圖存儲(chǔ)在鄰接矩陣中，在用戶界面輸入起點(diǎn)數(shù)。功能模塊：利用Floyd算法，初始化最短路徑，依次插入中間點(diǎn)判斷是否路徑更短，更新至最短路徑，循環(huán)結(jié)束，路徑入棧。輸出模塊：在文件中輸出打印起點(diǎn)到其余各點(diǎn)的最短路徑。（4） 模塊之間的層

9、次關(guān)系輸入模塊->功能模塊->輸出模塊3、 詳細(xì)設(shè)計(jì)（1） 實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型：利用鄰接矩陣存儲(chǔ)圖，邊間權(quán)值存儲(chǔ)在一維數(shù)組存儲(chǔ)Adjj*Num+k中，頂點(diǎn)數(shù)和權(quán)值均為整型int；最大值、起點(diǎn)數(shù)、最短權(quán)值、路徑、頂點(diǎn)域均為整型int。/利用鄰接矩陣存儲(chǔ)圖：class Graphprivate:int *Adj;/保存鄰接矩陣的一維數(shù)組j和k之間權(quán)值存儲(chǔ)在Adjj*Num+k中int Num;public:Graph();Graph();void Floyd(int start);const int MaxNum=100000; int*dist=new intNum;i

10、nt*prev=new intNum;int*s=new intNum;（2） 算法的具體步驟:1>.讀取文件中的頂點(diǎn)個(gè)數(shù)及各邊權(quán)值；2>.利用鄰接矩陣存儲(chǔ)圖，用戶輸入起點(diǎn)數(shù)，進(jìn)行Floyd算法；3>.初始化最短路徑，對(duì)角線元素設(shè)置為0，其他元素設(shè)置為邊的權(quán)值，沒有有向邊設(shè)置為MaxNum；4>.依次插入中間點(diǎn)k，判斷是否檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立；5>.若不成立，則路徑不改變；6>.若成立，則更新最短路徑，設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)；7>.遞歸訪問直至所有中間點(diǎn)

11、均被訪問，則循環(huán)結(jié)束，路徑入棧；8>.在文件中輸出打印最短路徑及花費(fèi)。流程圖：注：由于VISIO無法正常運(yùn)行，流程圖無法用此軟件繪制。（3） 算法的時(shí)空分析：Floyd算法的時(shí)間復(fù)雜度為O（n³）。4、 調(diào)試分析僅輸出最小花費(fèi)，而無法輸出最短路徑：解決方法：初始化一個(gè)棧，將路徑存入棧中，之后pop操作彈出路徑即可。5、 測(cè)試結(jié)果 a.案例輸入： 輸入：（文件） 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：0 輸出：（文件） 源點(diǎn)0到頂點(diǎn)1的最小花費(fèi)為:5

12、路徑為：0>2>1 源點(diǎn)0到頂點(diǎn)2的最小花費(fèi)為:3 路徑為：0>2 源點(diǎn)0到頂點(diǎn)3的最小花費(fèi)為:10 路徑為：0>2>1>3 源點(diǎn)0到頂點(diǎn)4的最小花費(fèi)為:18 路徑為：0>2>4b.輸入：（文件） 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：2 輸出：（文件） 源點(diǎn)2到頂點(diǎn)0：沒有連通路徑 源點(diǎn)2到頂點(diǎn)1的最小花費(fèi)為:2 路徑為：2>1 源點(diǎn)2到頂點(diǎn)3的最小花費(fèi)為:7 路徑為：2>1>3 源點(diǎn)2到頂點(diǎn)4的最

13、小花費(fèi)為:15 路徑為：2>4 c.輸入：（文件） 6 18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用戶） 輸入起點(diǎn)：5 輸出：（文件） 源點(diǎn)5到頂點(diǎn)0的最小花費(fèi)為:21 路徑為：5>1>3>4>0 源點(diǎn)5到頂點(diǎn)1的最小花費(fèi)為:8 路徑為：5>1 源點(diǎn)5到頂點(diǎn)2的最小花費(fèi)為:12 路徑為：5>2 源點(diǎn)5到頂點(diǎn)3的最小花費(fèi)為:13 路徑為：5>1>3 源點(diǎn)5到頂點(diǎn)4的最小花費(fèi)為:19 路徑

14、為：5>1>3>4d.輸入：（文件） 6 18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用戶） 輸入起點(diǎn)：3 輸出：（文件） 源點(diǎn)3到頂點(diǎn)0的最小花費(fèi)為:8 路徑為：3>4>0 源點(diǎn)3到頂點(diǎn)1的最小花費(fèi)為:11 路徑為：3>5>1 源點(diǎn)3到頂點(diǎn)2的最小花費(fèi)為:11 路徑為：3>4>0>2 源點(diǎn)3到頂點(diǎn)4的最小花費(fèi)為:6 路徑為：3>4 源點(diǎn)3到頂點(diǎn)5的最小花費(fèi)為:3 路徑為：3

15、>5e.輸入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：1 輸出：（文件） 源點(diǎn)1到頂點(diǎn)0：沒有連通路徑 源點(diǎn)1到頂點(diǎn)2：沒有連通路徑f.輸入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：3 輸出：（文件） 源點(diǎn)3到頂點(diǎn)0的最小花費(fèi)為:-572562307 路徑為：3>1>0 源點(diǎn)3到頂點(diǎn)1的最小花費(fèi)為:-572662307 路徑為：3>1 源點(diǎn)3到頂點(diǎn)2的最小花費(fèi)為:-572662307 路徑為：3>26、 用戶使用說明1. 本程序運(yùn)行環(huán)境為Win7 64位操作系統(tǒng)下VC6

16、.0，執(zhí)行文件為最短路徑問題.exe.2. 要求首先在文件中輸入頂點(diǎn)數(shù)及各邊的票價(jià)矩陣，再在用戶界面輸入起點(diǎn)數(shù)。輸入范例： 輸入：（文件） 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用戶） 輸入起點(diǎn)：0 輸出：（文件） 源點(diǎn)0到頂點(diǎn)1的最小花費(fèi)為:5 路徑為：0>2>1 源點(diǎn)0到頂點(diǎn)2的最小花費(fèi)為:3 路徑為：0>2 源點(diǎn)0到頂點(diǎn)3的最小花費(fèi)為:10 路徑為：0>2>1>3 源點(diǎn)0到頂點(diǎn)4的最小花費(fèi)為:18 路徑為：0>2>47、 實(shí)驗(yàn)心得

17、本次實(shí)驗(yàn)要求讀取文件中的頂點(diǎn)數(shù)及各邊權(quán)值，輸入起點(diǎn)數(shù)，在文件中輸出起點(diǎn)到其余各點(diǎn)的最短路徑及花費(fèi)，由于涉及全局任意兩點(diǎn)最短路徑，因此我采用Floyd算法，通過初始化路徑，不斷插入中間點(diǎn)進(jìn)行比較路徑長短，更新最短路徑直至循環(huán)結(jié)束，輸出最短路徑及花費(fèi)。Floyd算法較Dijkstra算法容易實(shí)現(xiàn)，但時(shí)間復(fù)雜度大，適合任意兩點(diǎn)間的最短路徑問題，如果確定起點(diǎn)終點(diǎn)則采用Dijkstra算法。8、 源程序#include <iostream>#include <stack>#include <fstream>using namespace std;const int M

18、axNum=100000;class Graphprivate:int *Adj;/保存j和k之間權(quán)值存儲(chǔ)在一位數(shù)組Adjj*Num+k中int Num;public:Graph();Graph(); void Floyd(int start);/*構(gòu)造函數(shù)*/Graph:Graph()ifstream input("input.txt",ios:in);if(input=NULL)cout<<"打開失敗啦!n"if(input!=NULL)input>>Num;Adj=new intNum*Num;if(Adj=NULL)exi

19、t(0);for(int i=0;i<Num;i+)for(int j=0;j<Num;j+)input>>Adji*Num+j;if(Adji*Num+j=-1)Adji*Num+j=MaxNum;/*析構(gòu)函數(shù)*/Graph:Graph()delete Adj;/*弗洛伊德算法*/void Graph:Floyd(int start)int*dist=new intNum;/最短權(quán)值int*prev=new intNum;/路徑int*s=new intNum;/s為已經(jīng)訪問的頂點(diǎn)域int i,j,k,m;m=start;for(i=0;i<Num;i+) /初

20、始化disti=Adjm*Num+i;previ=m;si=0;prevm=-1;sm=1;for(i=0;i<Num-1;i+) /Num-1次遞歸int min;for(k=0;k<Num;k+)if(!sk) break;min=distk;j=k;for(k=j+1;k<Num;k+)if(!sk&&distk<min)min=distk;j=k;sj=1;for(k=0;k<Num;k+) /更新最短路徑if(!sk&&distj+Adjj*Num+k<distk)distk=distj+Adjj*Num+k;prevk=j;ofstream output("output.txt",ios:ou