實驗報告6-最短路徑問題

1、數(shù)據(jù)結構課程實驗指導書HUNAN UNIVERSITY課程實習報告題目最短路徑問題學生姓名 學生學號 專業(yè)年級 指導老師 完成日期 1、 需求分析本實驗是求最短路徑的問題，從文件中讀入有向網(wǎng)中頂點的數(shù)量和頂點間的票價的矩陣，以用戶指定的起點，在文件中輸出到其余各頂點的最短路徑及花費。（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 （用戶） 輸入起點：0輸入值的范圍：文件輸入中，頂點數(shù)和矩陣中頂點間的票價均為整型int，用戶輸入中，起點數(shù)為整型int。（2） 輸

2、出的形式：（文件）源點0到頂點1的最小花費為:5路徑為：0>2>1源點0到頂點2的最小花費為:3路徑為：0>2源點0到頂點3的最小花費為:10路徑為：0>2>1>3源點0到頂點4的最小花費為:18路徑為：0>2>4（3） 程序所達到的功能：在文件中給出有向網(wǎng)的頂點個數(shù)和頂點間的票價的矩陣，以用戶指定的起點，在文件中輸出起點到其余各頂點的最短路徑及花費。（4）測試數(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、入起點：0 輸出：（文件） 源點0到頂點1的最小花費為:5 路徑為：0>2>1 源點0到頂點2的最小花費為:3 路徑為：0>2 源點0到頂點3的最小花費為:10 路徑為：0>2>1>3 源點0到頂點4的最小花費為: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 （用戶） 輸入起點：2 輸出：（文件） 源點2到頂點0：沒有連通路徑 源點2到頂點1的最小花費為:2 路徑為：2>1 源點2到頂點3的最小

4、花費為:7 路徑為：2>1>3 源點2到頂點4的最小花費為: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 （用戶） 輸入起點：5 輸出：（文件） 源點5到頂點0的最小花費為:21 路徑為：5>1>3>4>0 源點5到頂點1的最小花費為:8 路徑為：5>1 源點5到頂點2的最小花費為:12 路徑為：5>2 源點5到頂點3的最小花費為:13 路徑為：

5、5>1>3 源點5到頂點4的最小花費為: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 （用戶） 輸入起點：3 輸出：（文件） 源點3到頂點0的最小花費為:8 路徑為：3>4>0 源點3到頂點1的最小花費為:11 路徑為：3>5>1 源點3到頂點2的最小花費為:11 路徑為：3>4>0>2 源點3到頂點4的最小花費為:6

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

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

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

9、次關系輸入模塊->功能模塊->輸出模塊3、 詳細設計（1） 實現(xiàn)概要設計中定義的所有數(shù)據(jù)類型：利用鄰接矩陣存儲圖，邊間權值存儲在一維數(shù)組存儲Adjj*Num+k中，頂點數(shù)和權值均為整型int；最大值、起點數(shù)、最短權值、路徑、頂點域均為整型int。/利用鄰接矩陣存儲圖：class Graphprivate:int *Adj;/保存鄰接矩陣的一維數(shù)組j和k之間權值存儲在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>.讀取文件中的頂點個數(shù)及各邊權值；2>.利用鄰接矩陣存儲圖，用戶輸入起點數(shù)，進行Floyd算法；3>.初始化最短路徑，對角線元素設置為0，其他元素設置為邊的權值，沒有有向邊設置為MaxNum；4>.依次插入中間點k，判斷是否檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立；5>.若不成立，則路徑不改變；6>.若成立，則更新最短路徑，設置Dis(i,j) = Dis(i,k) + Dis(k,j)；7>.遞歸訪問直至所有中間點

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

12、路徑為：0>2>1 源點0到頂點2的最小花費為:3 路徑為：0>2 源點0到頂點3的最小花費為:10 路徑為：0>2>1>3 源點0到頂點4的最小花費為: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 （用戶） 輸入起點：2 輸出：（文件） 源點2到頂點0：沒有連通路徑 源點2到頂點1的最小花費為:2 路徑為：2>1 源點2到頂點3的最小花費為:7 路徑為：2>1>3 源點2到頂點4的最

13、小花費為: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 （用戶） 輸入起點：5 輸出：（文件） 源點5到頂點0的最小花費為:21 路徑為：5>1>3>4>0 源點5到頂點1的最小花費為:8 路徑為：5>1 源點5到頂點2的最小花費為:12 路徑為：5>2 源點5到頂點3的最小花費為:13 路徑為：5>1>3 源點5到頂點4的最小花費為: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 （用戶） 輸入起點：3 輸出：（文件） 源點3到頂點0的最小花費為:8 路徑為：3>4>0 源點3到頂點1的最小花費為:11 路徑為：3>5>1 源點3到頂點2的最小花費為:11 路徑為：3>4>0>2 源點3到頂點4的最小花費為:6 路徑為：3>4 源點3到頂點5的最小花費為:3 路徑為：3

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

16、.0，執(zhí)行文件為最短路徑問題.exe.2. 要求首先在文件中輸入頂點數(shù)及各邊的票價矩陣，再在用戶界面輸入起點數(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 （用戶） 輸入起點：0 輸出：（文件） 源點0到頂點1的最小花費為:5 路徑為：0>2>1 源點0到頂點2的最小花費為:3 路徑為：0>2 源點0到頂點3的最小花費為:10 路徑為：0>2>1>3 源點0到頂點4的最小花費為:18 路徑為：0>2>47、 實驗心得

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

18、axNum=100000;class Graphprivate:int *Adj;/保存j和k之間權值存儲在一位數(shù)組Adjj*Num+k中int Num;public:Graph();Graph(); void Floyd(int start);/*構造函數(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;/*析構函數(shù)*/Graph:Graph()delete Adj;/*弗洛伊德算法*/void Graph:Floyd(int start)int*dist=new intNum;/最短權值int*prev=new intNum;/路徑int*s=new intNum;/s為已經訪問的頂點域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