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

《实验11：图的最短路径实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：图的最短路径实验学院：计算机与软件学院专业：指导教师：杨芳报告人：学号：班级：实验时间：2014-11-6实验报告提交时间：教务处制－5－一、实验目的1、掌握图结构的（邻接矩阵）输入方法2、掌握图结构的说明、创建以及图的存储表示（邻接矩阵）3、掌握最短路径算法原理4、掌握最短路径算法的编程实现方法二、实验要求1、熟悉C++语言编程2、熟悉图的邻接矩阵存储表示3、熟悉最短路径算法原理4、熟练使用C++语言，实现最短路径算法三、实验内容本次

2、实验有两项内容：（一）图的最短路径实验1、问题描述给定一个顶点（始点），求该顶点（始点）到（连通）图中其它顶点的最短路径。2、算法⑴、初始化：S←{v1};//始点送SD[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←SU{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/

3、/更新从v1到vi的路径⑷、判断：若S=V,则算法结束，否则转⑵。3、输入第一行：样本顶点个数，假设为n。第二行，n个顶点（用空格隔开）第三行开始到n+2行：每一行是某顶点（按第二行的输入为序）与其它顶点的距离（-1表示无穷大）第n+3行：开始顶点4、输入样本5abcde-15-1715-1-15-1-1-1-1-1-11－5－-1-12-1-1-1-1-1-1-1a5、输出共计n行（图中顶点数目）每行是（与输入顺序相同）某顶点（距离）：路径（顶点序列，用空格隔开，回车前无空格）6、输出样本a(0)

4、:b(5):abc(9):adcd(7):ade(10):adce（二）拓扑排序（选作）1、问题描述已知有向图，顶点从0开始编号，求它的求拓扑有序序列。2、拓扑排序算法：给出有向图邻接矩阵（1）逐列扫描矩阵，找出入度为0且编号最小的顶点v（2）输出v，并标识v已访问（3）把矩阵第v行全清0重复上述步骤，直到所有顶点输出为止3、输入第一行输入一个整数t，表示有t个有向图第二行输入n，表示图有n个顶点第三行起，输入n行整数，表示图对应的邻接矩阵以此类推输入下一个图的顶点数和邻接矩阵4、输出每行输出一个图

5、的拓扑有序序列5、样本输入250101100100000010010000000－5－700000001011000100000010100000000011010000000010106、样本输出013244651320四、程序清单五、程序运行时截图六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想）－5－指导教师批阅意见：成绩评定：指导教师签字：年月日备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。－5－