深 圳 大 学 实 验 报 告
课程名称： 数据结构实验与课程设计
实验项目名称： 图的最短路径实验
学院： 计算机与软件学院
专业： 计科
指导教师： 杨芳
报告人： 许运生 学号：2013150381 班级： 08
实验时间： 2014-11-6
实验报告提交时间： 2014/11/6
教务处制
一、实验目的
1、掌握图结构的（邻接矩阵）输入方法
2、掌握图结构的说明、创建以及图的存储表示（邻接矩阵） 3、掌握最短路径算法原理
4、掌握最短路径算法的编程实现方法
二、实验要求
1、熟悉C++语言编程
2、熟悉图的邻接矩阵存储表示 3、熟悉最短路径算法原理
4、熟练使用C++语言，实现最短路径算法
三、实验内容 本次实验有两项内容：
（一）图的最短路径实验 1、问题描述
给定一个顶点（始点），求该顶点（始点）到（连通）图中其它顶点的最短路径。 2、算法
⑴、初始化： S ← {v1 }; // 始点送S
D[i] ← arc[1][i], i = 2, 3, …, n; // 从v1到vi的距离 P[i] = {1,i} // 从v1到vi的路径 ⑵、求出最短路径的长度：
D[j] ← min { D[i] }, iV-S ; S←S U {j }; ⑶、修改：
if (D[i] > D[j] + arc[j][i]) {
D[i] = D[j]+arc[j][i];
P[i] = P[j] U {i} ; } iV-S // 更新从v1到vi的路径
⑷、判断：若 S = V, 则算法结束，否则转 ⑵。
3、输入
第一行：样本顶点个数，假设为n。 第二行，n个顶点（用空格隔开）
第三行开始到n+2行：每一行是某顶点（按第二行的输入为序）与其它顶点的距离（-1表示无穷大）
第n+3行：开始顶点
4、输入样本
5
a b c d e -1 5 -1 7 15 -1 -1 5 -1 -1 -1 -1 -1 -1 1 -1 -1 2 -1 -1
－2－
-1 -1 -1 -1 -1 a 5、输出
共计n行（图中顶点数目）
每行是（与输入顺序相同）某顶点（距离）：路径（顶点序列，用空格隔开，回车前无空格）
6、输出样本
a(0): b(5): a b c(9): a d c d(7): a d
e(10): a d c e （二）拓扑排序（选作）
1、问题描述
已知有向图，顶点从0开始编号，求它的求拓扑有序序列。
2、拓扑排序算法：给出有向图邻接矩阵
（1）逐列扫描矩阵，找出入度为0且编号最小的顶点v （2）输出v，并标识v已访问 （3）把矩阵第v行全清0
重复上述步骤，直到所有顶点输出为止
3、输入
第一行输入一个整数t，表示有t个有向图 第二行输入n，表示图有n个顶点
第三行起，输入n行整数，表示图对应的邻接矩阵 以此类推输入下一个图的顶点数和邻接矩阵
4、输出
每行输出一个图的拓扑有序序列
5、样本输入 2 5
0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0
－3－
1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0
6、样本输出 0 1 3 2 4 4 6 5 1 3 2 0
四、程序清单 程序一：
#include using namespace std; /**实验十一 图的最短路径实验 */ //常数
const int MAX_VERT = 20; const int MAX_NUM = 1000; //数组
bool final[MAX_VERT]; int Dest[MAX_VERT];
char Path[MAX_VERT][MAX_VERT]; //图结构体
struct Graphic{ int vertNum; char vertValue[MAX_VERT]; int AdjMatrix[MAX_VERT][MAX_VERT]; };
//图的初始化
void initGraphic(Graphic &G, int n){ int i, j; G.vertNum = n; //输入顶点的值 for(i = 1; i <= G.vertNum; i++) cin>>G.vertValue[i]; //输入顶点的邻接矩阵 for(i = 1; i <= G.vertNum; i++){ for(j = 1; j <= G.vertNum; j++){ cin>>G.AdjMatrix[i][j]; if(G.AdjMatrix[i][j] == -1)
－4－
G.AdjMatrix[i][j] = MAX_NUM; } } }
//最短路径查找
void shortestPath(Graphic G, char vert){ int i, j, k, cv, Min; //查找初始顶点的下标 for(i = 1; i <= G.vertNum; i++){ if(G.vertValue[i] == vert){ cv = i; break; } } //访问集初始化和路径集初始化 for(i = 1; i <= G.vertNum; i++){ Path[i][0] = 0; Dest[i] = MAX_NUM; if(G.AdjMatrix[cv][i] < MAX_NUM){ Dest[i] = G.AdjMatrix[cv][i]; Path[i][1] = G.vertValue[cv]; Path[i][2] = G.vertValue[i]; Path[i][0] = 2; } final[i] = false; } // final[cv] = true; Dest[cv] = 0; //查找路径最短,查找G.vertNum-1次 for(i = 1; i < G.vertNum; i++){ Min = MAX_NUM; for(j = 1; j <= G.vertNum; j++){ if(!final[j] && Dest[j] < Min){ cv = j; Min = Dest[j]; } } final[cv] = true; //更新最短路径 for(j = 1; j <= G.vertNum; j++){ if((!final[j]) && (Min + G.AdjMatrix[cv][j] < Dest[j])){ Dest[j] = Min + G.AdjMatrix[cv][j]; for(k = 0; k <= Path[cv][0]; k++){
－5－
Path[j][k] = Path[cv][k]; } Path[j][0]++; Path[j][Path[j][0]] = G.vertValue[j]; } } } //输出初始顶点到其他各顶点的最短路径 for(i = 1; i <= G.vertNum; i++){ cout<//主函数 int main() { int n; char ch; Graphic G; //文本输入 //freopen(\"cin.txt\ //顶点个数 cin>>n; //图的初始化 initGraphic(G, n); //最短路径查找，初始顶点为ch cin>>ch; shortestPath(G, ch); //结束 return 0; } 程序二：#include using namespace std; //常量const int MAX_VERT = 10; //图的结构体 struct Graphic{ int vertNum; int VertValue[MAX_VERT];
－6－
int AdjMatrix[MAX_VERT][MAX_VERT]; bool visited[MAX_VERT]; };
//图初始化
void initGraphic(Graphic &G, int n){ G.vertNum = n; int i, j; //输入邻接矩阵 for(i = 0; i < G.vertNum; i++){ for(j = 0; j < G.vertNum; j++) cin>>G.AdjMatrix[i][j]; } //顶点赋值 for(i = 0; i< G.vertNum; i++){ G.VertValue[i] = i; G.visited[i] = false; } }
//拓扑排序
void TopoSort(Graphic G){ int i, j, k, m; for(m = 0; m //主函数 int main() { int t, n, i; Graphic G[2]; //文本输入 //freopen(\"cin2.txt\－7－
}
//输入有向图个数 cin>>t;
for(i = 0; i < t; i++){ //输入顶点个数 cin>>n; //图初始化 initGraphic(G[i], n); //拓扑排序 TopoSort(G[i]); }
//结束 return 0;
五、程序运行时截图 程序一
程序二
六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想） 路径的更新比较模糊。。。
－8－
指导教师批阅意见： 成绩评定： 指导教师签字： 年 月 日 备注： －9－
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
－10－
