基于Floyd算法的最短路径问题的求解c++(完整资料).doc

基于Floyd算法的最短路径问题的求解c++(完整资料）(可以直接使用，可编辑优秀版资料，欢迎下载）摘要现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是floyd算法。通过flｏｙd算法使最短路径问题变得简单化。采用图的邻接矩阵或邻接表实现最短路径问题中图的存储。采用VisualＣ+＋6．０的控制台工程和MＦC工程分别实现基于floyd算法求最短路径的应用.关键词:最短路径；ｆｌｏyd算法;邻接矩阵;ＭＦC工程目录1需求分析12算法基本原理12．1邻接矩阵12。２弗洛伊德算法2３类设计２３。１类的概述2３．２类的接口设计33.3类的实现44基于控制台的应用程序74.1主函数设计7４。2运行结果及分析8５基于ＭFＣ的应用程序95．1图形界面设计95.1程序代码设计115.３运行结果及分析2０结论21参考文献2２需求分析Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法.该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线.假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点Ａ到B所含边的数目最少的路径。我们只需从顶点A出发对图作广度优先搜索，一旦遇到顶点Ｂ就终止。由此所得广度优先生成树上,从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径中的中转站数.但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说，可能更关心的是节省交通费用；对于司机来说里程和速度则是他们感兴趣的信息.为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目,而是路径上边的权值之和.边赋以权值之后再结合最短路径算法来解决这些实际问题.Floyd算法是最短路径经典算法中形式较为简单，便于理解的一种。算法基本原理２．1邻接矩阵邻接矩阵（ＡdjaceｎcyMatrix）：是表示顶点之间相邻关系的矩阵.设G=（V,Ｅ）是一个图，其中Ｖ=｛v1,v２，…,vn}。G的邻接矩阵是一个具有下列性质的ｎ阶方阵:（1)对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论无向简单图)，有向图则不一定如此.（2）在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和,而入度为第i列所有元素的和。（3）用邻接矩阵法表示图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n／２个空间。2．2弗洛伊德算法弗洛伊德算法使用图的邻接矩阵arcｓ[ｎ+1］［ｎ+１］来存储带权有向图.算法的基本思想是：设置一个ｎxn的矩阵A（k），其中除对角线的元素都等于0外,其它元素a(k)[i]［ｊ］表示顶点i到顶点j的路径长度,K表示运算步骤.开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K＝０时，Ａ（0）［i][j］=aｒcｓ［i］［j］,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为:第一步,让所有边上加入中间顶点1，取A［i］[j]与A[ｉ］[1］＋A［１］[j］中较小的值作A[i］［j]的值，完成后得到A(1）；第二步，让所有边上加入中间顶点２,取A[i][j］与A［i］［２］+A［2］[j]中较小的值,完成后得到A（2）…,如此进行下去，当第n步完成后，得到A（n），A(n）即为我们所求结果，A（n)[i]［j]表示顶点i到顶点j的最短距离。因此弗洛伊德算法可以描述为：Ａ（0）［i][j]＝arcｓ［i]［j]；/／arcs为图的邻接矩阵A（k）[i］［j］=miｎ｛Ａ（k－1)［i]［j］，A（k—１）[i][k］+Ａ（k－1）[k］［ｊ]｝，其中ｋ=１，２，…，n（1)定义一个n阶方阵序列:D（—１)，Ｄ（0），…,Ｄ(n－1）.Ｄ（—１）[i][j］=G。ａrcs［i］［ｊ］；D（ｋ）［i］［j]=min{Ｄ（k-1)［i］[j]，D(k—1）［ｉ][k]+D(ｋ—1）[k]［j］｝,k=０,１，…，n-1（2）其中Ｄ（0）［i］[j］是从顶点vi到vj中间顶点是v０的最短路径的长度;D(k）[ｉ]［j]是从顶点ｖi到vj中间顶点的序号不大于k的最短路径长度；D（n-１）［ｉ］［j］是从顶点ｖi到vj的最短路径长度。类设计3。1类