实验11：图最短路径实验报告.docVIP

－ PAGE 5－ 深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 图的最短路径实验 学院： 计算机与软件学院 专业： 指导教师： 杨芳 报告人： 学号： 班级： 实验时间： 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] }, i?V-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} ; } i?V-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 -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 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 四、程序清单 五、程序运行时截图 六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想） 指导教师批阅意见： 成绩评定： 指导教师签字： 年 月 日备注：注：1、报告内的项目或内容设