合肥工业大学离散数学实验报告.doc

实验一：最短路径算法实现姓 名： 李亚鸣 学 号： 班 级： 计算机科学与技术14-1班 实验地点： 三号实验楼1号机房 实验时间： 2015年9月26日 1 实验目的和要求实验目的：深刻理解图论中两点之间最短路径求解的相关算法；并借助提供的实验平台完成编码，实现最短路径输出*理解Dijkstra算法实现最短路径算法，并利用所提供的MFC代码图形化显示。初步了解部分基础MFC知识。 实验要求：(1)理解Dijkstra算法并编码实现图中某一顶点到其它顶点最短路径的求解；(2)理解Floyd-Warshall算法并编码实现图中任意两顶点之间最短路径的求解；(3)可以写对编程的要求(4)在待完善的MFC代码上补充Dijkstra算法的核心部分，并在图形上实现。实验目的和要求必须在此基础上修改或补充，否则实验报告重写！2 实验环境和工具VisualC+6.03 实验结果3.1 算法流程图3.2 程序核心代码 template <typename Type>void Graph<Type>:ChangeWeight(int u,int v) /请写出实现代码int temp=Du+arcsuv;if(temp<Dv)Dv=temp;prev=u;template <typename Type>void Graph<Type>:ShortestPath_DIJ() init_source(verfrom) ;/对每个顶点的路径长度和前驱顶点初始化int i,j,u,min;/ u是当前循环比较得出的拟加入集合S的顶点，经过循环比较得出的最短路径Dj存入minbool SMAX;/Si值为false代表i顶点还没被并入集合Sfor(i=1;i<=vexnum;i+)/初始化Si=false;/顶点i还没有被并入S集合for(i=1;i<=vexnum;i+)/请写出后续代码Di=arcsv0i;if(Di=INFINITY)prei=0;else prei=v0;Dv0=0;Sv0=true;for(i=2;i<=vexnum;i+)int temp=INFINITY;u=v0;for(j=1;j<=vexnum;j+)if(!Sj&&Dj<temp)u=j;temp=Dj;Su=true;for(j=1;j<=vexnum;j+)if(!Sj&&arcsuj<INFINITY)ChangeWeight(u,j);3.3 运行结果3.4 运行结果分析4 思考题（可选）当修改循环变量从0到（顶点个数 - 1）时，程序运行结果是否正确？试分析原因。5 实验心得初步了解变量名以后，准备开始写核心部分的代码，但是具体的Dijkstra算法的代码还是有些难以实现，参考了书籍的思想，有了思路，开始动手写代码，Dijstra的核心还是贪心，所以每次要根据已经加入S集合的所有点，找出他们相邻的最短的一条边，最后的图形化实现并不是自己实现的，只是了解了基本的操作方式。总体来说，通过这次实验也更加熟悉了Dijstra算法的核心思想和具体的实现。