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

深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 图的最短路径实验 学院： 计算机与软件学院 专业： 指导教师： 杨芳 报告人： 学号： 班级： 实验时间： 2014-11-6 实验报告提交时间： 教务处制一、实验目的 1、掌握图结构的（邻接矩阵）输入方法2、掌握图结构的说明、创建以及图的存储表示（邻接矩阵）3、掌握最短路径算法原理4、掌握最短路径算法的编程实现方法二、实验要求 1、熟悉C+语言编程2、熟悉图的邻接矩阵存储表示3、熟悉最短路径算法原理4、熟练使用C+语言，实现最短路径算法三、实验内容 本次实验有两项内容：（一）图的最短路径实验1、问题描述给定一个顶点（始点），求该顶点（始点）到（连通）图中其它顶点的最短路径。2、算法、初始化： S v1 ; / 始点送SDi arc1i, i = 2, 3, , n;/ 从v1到vi的距离Pi = 1,i / 从v1到vi的路径、求出最短路径的长度：Dj min Di , iV-S ; SS U j ;、修改： if (Di Dj + arcji) Di = Dj+arcji; Pi = Pj U i ; iV-S / 更新从v1到vi的路径、判断：若 S = V, 则算法结束，否则转 。3、输入第一行：样本顶点个数，假设为n。第二行，n个顶点（用空格隔开）第三行开始到n+2行：每一行是某顶点（按第二行的输入为序）与其它顶点的距离（-1表示无穷大）第n+3行：开始顶点4、输入样本5a 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 -1a5、输出共计n行（图中顶点数目）每行是（与输入顺序相同）某顶点（距离）：路径（顶点序列，用空格隔开，回车前无空格）6、输出样本a(0):b(5): a bc(9): a d cd(7): a de(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、样本输入250 1 0 1 10 0 1 0 00 0 0 0 10 0 1 0 00 0 0 0 070 0 0 0 0 0 01 0 1 1 0 0 01 0 0 0 0 0 01 0 1 0 0 0 00 0 0 0 0 1 10 1 0 0 0 0 00 0 0 1 0 1 06、样本输出0 1 3 2 4 4 6 5 1 3 2 0 四、程序清单五、程序运行时截图六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想）指导教师批阅意见：成绩评定： 指导教师签字： 年 月