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

《离散数学》实验报告

实验一：最短路径算法实现

姓 名： 李亚鸣 学 号： 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::ChangeWeight(int u,int v) {

//请写出实现代码

《离散数学》实验报告

}

int temp=D[u]+arcs[u][v]; if(temp

D[v]=temp; pre[v]=u;

template

void Graph::ShortestPath_DIJ() {

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算法的核心思想和具体的实现。

本文来源：https://www.bwwdw.com/article/onwf.html