浙江大學城市學院實驗報告

課程名稱 數(shù)據(jù)結(jié)構(gòu)與算法

實驗項目名稱 實驗八 圖的最短路徑問題

實驗成績 指導老師(簽名 ) 日期

實驗?zāi)康暮鸵?/p>

掌握圖的最短路徑概念。

理解并能實現(xiàn)求最短路徑的DijKstra算法(用鄰接矩陣表示圖)。

二. 實驗內(nèi)容

1、編寫用鄰接矩陣表示有向帶權(quán)圖時圖的基本操作的實現(xiàn)函數(shù)，基本操作包括：

① 初始化鄰接矩陣表示的有向帶權(quán)圖 void InitMatrix(adjmatrix G);

② 建立鄰接矩陣表示的有向帶權(quán)圖 void CreateMatrix(adjmatrix G, int n) (即通過輸入圖的每條邊建立圖的鄰接矩陣);

③ 輸出鄰接矩陣表示的有向帶權(quán)圖void PrintMatrix(adjmatrix G, int n) (即輸出圖的每條邊)。

把鄰接矩陣的結(jié)構(gòu)定義以及這些基本操作函數(shù)存放在頭文件Graph2.h中。

2、編寫求最短路徑的DijKstra算法函數(shù) void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，該算法求從頂點i到其余頂點的最短路徑與最短路徑長度，并分別存于數(shù)組 path 和 dist 中。編寫打印輸出從源點到每個頂點的最短路徑及長度的函數(shù)void PrintPath(int dist[], edgenode *path[], int n)。

3、編寫測試程序(即主函數(shù))，首先建立并輸出有向帶權(quán)圖，然后計算并輸出從某頂點v0到其余各頂點的最短路徑。

要求：把指針數(shù)組的基類型結(jié)構(gòu)定義edgenode、求最短路徑的DijKstra算法函數(shù)、打印輸出最短路徑及長度的函數(shù)PrintPath以及主函數(shù)存放在文件test9_2.cpp中。

測試數(shù)據(jù)如下：

0

0

1

2

3

5

4

4

8

2

3

10

7

6

5

9

6

15

4、填寫實驗報告，實驗報告文件取名為report8.doc。

5、上傳實驗報告文件report8.doc與源程序文件test9_2.cpp及Graph2.h到Ftp服務(wù)器上自己的文件夾下。

三. 函數(shù)的功能說明及算法思路

包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路

【結(jié)構(gòu)說明】

const int MaxVertexNum=10; //圖的最大頂點數(shù)

const int MaxEdgeNum=100; //邊數(shù)的最大值

const int MaxValue=32767; //權(quán)值的無窮大表示

typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //鄰接矩陣

typedef struct Node {

int adjvex;

struct Node *next;

} edgenode;//路徑結(jié)點

【函數(shù)說明】

① void InitMatrix(adjmatrix &G)

功能：初始化鄰接矩陣表示的有向帶權(quán)圖

思路：將鄰接矩陣中的所有權(quán)值設(shè)置為無窮大(MaxValue)

② void CreateMatrix(adjmatrix &G, int n)

功能：建立鄰接矩陣表示的有向帶權(quán)圖(即通過輸入圖的每條邊建立圖的鄰接矩陣)

思路：按照輸入的頂點信息和權(quán)值信息，更新鄰接矩陣內(nèi)對應(yīng)的值

③ void PrintMatrix(adjmatrix G, int n)

功能：輸出鄰接矩陣表示的有向帶權(quán)圖 (即輸出圖的每條邊)

思路：按照一定的格式輸出鄰接矩陣

④ void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n)

功能：求最短路徑的DijKstra算法函數(shù)

思路：按照從源點到其余每一頂點的最短路徑長度遞增的次序依次求出從源點到每個頂點的最短路徑及長度。設(shè)立一個集合S，用以保存已求得最短路徑的終點，其初值為只有一個元素，即源點；一個數(shù)組 dist[n]，其每個分量 dist[j] 保存從源點經(jīng)過S集合中頂點最后到達頂點 j 的路徑中最短路徑的長度，其初值為從源點到每個終點的弧的權(quán)值(沒弧則置為∞)；一個指針數(shù)組path[n]，path[j]指向一個單鏈表，保存相應(yīng)于dist[j]的從源點到頂點 j 的最短路徑(即頂點序列)，初值為空。

⑤ void PATH(edgenode *path[], in

總結(jié)

以上是生活随笔為你收集整理的数据结构最短路径例题_数据结构算法实验8图的最短路径问题附源代码.doc的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。