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