软件课程设计报告- 从某个源点到其余各顶点的最短路径.doc

北京信息科技大学 计算机软件基础课程设计 题 目： 从某个源点到其余各顶点的最短路径 学 院： 光电信息与通信工程学院 专 业： 通信工程专业 学生姓名： 班级/学号 指导老师： 曹林 李振松 张月霞 杨玮 起止时间： 题目 从某个源点到其余各顶点的最短路径（难度系数10，全部做出给100分） 主要 内容 设计 要求 主要 仪器 设备 Windows XP 操作系统、Microsoft Visual C++ 6.0、MSDN Library。 主要 参考 文献 侯俊杰. 深入浅出MFC(第二版)[M]. 武汉：华中科技大学出版社, 2001. 北京出版社, .. [3] 孟彩霞. 计算机软件基础[M]. 陕西：西安电子科技大学出版社, 2003. [4] 严蔚敏, 吴伟民. 数据结构[M]. 北京：清华大学出版社, 2005. 课程设计进度计划（起止时间、工作内容） 课程设计开始日期 课程设计完成日期 课程设计实验室名称 地 点  摘要 本次课程设计的问题：假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，它们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；北京到武汉的最短路径。 本次课程设计中应用Floyd算法求最短路径。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵，从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，按一个公式，构造出矩阵D(1)，又用同样地公式由D(1)构造出D(2)…最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 本次试验可以进行有向和无向的计算，不同城市之间的距离由开始进行输入，最后显示两个城市之间的最短路径。 一、应用弗洛伊德（Floyd）算法计算最短路径 假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。 二、弗洛伊德（Floyd）算法的基本思想 Floyd 算法是通过权矩阵计算来实现的一种方法，其主要思想是从代表任意两个节点vi到vj的距离的带权邻接矩阵D(0)开始，首先计算D(1)，即计算vi到vj的距离。经过一次经转的所有可能路径，经过比较后选出最短路，代替D(0)中对应的路径，迭代列出距离矩阵D(1)，D(1)中各元素表示通过一次迭代后网络中任意两点间最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。在此基础上依次计算D(2) ,D(3) ,…,D(k)，D(k)中对应的元素表示任意两点间不经过中间点或最多允许经过2k-1 个中间点时的最短路。当D(k+1)=D(k)时，表明得到的带权邻接矩阵D(k)就反映了所有顶点对之间的最短距离信息,，成为最短距离矩阵。 三、floyd算法函数 四、基本流程 Floyd采用动态规划余力和逐步优化激素和，对有向带权图G=（V, E）设计出求每对定点见最短路径的方法。该刚发使用邻接矩阵表示有向带权图G，有向图中的n个顶点从1开始编号。初始时，用邻接矩阵adges存储有向图G，即顶点i到j的最短路径长度adges[i][j]就是弧所对应的权值，它表示任意顶点对之间不经过任何中间顶点的最短路径和长度。要求顶点i到j记得最短路径长度，对每一对顶点的路径进行比较存储的试探，累加递归后产生一个n阶路径矩阵序列A，算法结束时，从该矩阵可以查找到i到j的最短路径上的所有点。 void pathchange(int i,int j,int k)//路径处理函数 { int m,n,p,q; for(m=0;mmax;m++) { path[i][j].distance[m]=-1; }//首先将其初始化 计算两点之间的距离 for(q=0;qmax;q++) { if(path[i][k].distance[q]!=-1) { m++; } else { break; } }//获取path[i][k]的长度为m for(q=0;qmax