Flyod算法求最短路径.doc

一、问题分析和任务定义：课题16选择合适的结构表示图，在此基础上实现求解最短路径的Floyd算法。要求：对所设计的图结构，提供必要的基本功能。1.1问题分析：本课题要求用Floyd算法解决两个点间的的最短路径问题，首先需要有一个有向图，可以选用邻接矩阵、邻接表和边集数组三种来存储的，考虑到稀疏矩阵的问题，我们可以采用了领接矩阵来进行存储，存储每对节点的起点，终点和权值。对于两点间的最短路径的算法，应可以求我们输入的任意两点的最短路径，也可以求所有节点的最短路径，最短路径也即是两节点间所有通路中最短的一条，将它输出。可以方便我们让一些具体的事件的最优化。比如说交通图的最短路程问题等，都可以在本算法上进行引升，会非常的方便。1.2解决思路：提供一个输入接口和标准的输入形式，让用户可以通过输入一组数据建立一个图，在屏幕上以邻接矩阵显示。通过floyd算法计算，可得出图中每对顶点的最短路径和路径长度。提供一个查询接口，通过输入起始顶点和终止顶点的代号，输出最短路径和路径长度。也可以查询全部的最短路径，让操作者自行选择。2、任务定义：要注意以下的问题输入输出的问题：2.1输入数据：顶点n(范围0-MVNUM)和边数e(范围0 - (n*(n-1)/2)，顶点信息i,j（字符型）(范围0 - MVNUM)，边的权值 w ( 整型)2.2输出数据：建立的邻接矩阵，有向图的邻接矩阵，最短路径和最短路径长度（范围0MANUM）2.3算法所能达到的功能：求得任意两点间最短路径和路径长度输出显示。3、测试数据： 测试的数据组第一组第二组节点数边数3 33 3边的信息1 2 72 3 91 3 21 2 32 3 41 3 11矩阵输出 7 9 3 11 4 输出最短路径： 1-2:路径长度为：7 路径为：1-2 1-3:路径长度为：2 路径为：1-3 2-1:不存在路径 2-3:路径长度为9 路径为：2-3 3-1:不存在路径 3-2:不存在路径 1-2:路径长度为： 3 路径为：1-2 1-3:路径长度为： 7 路径为：1-2-3 2-1:不存在路径 2-3:路径长度为： 4 路径为：2-3 3-1:不存在路径 3-2:不存在路径 二、概要设计和数据结构的选择： 本次课程设计的数据的相关定义和主要程序段如下： 1、数据类型的定义typedef char VertexTYpe;/定义顶点的值类型typedef int Adjmatrix;/定义顶点的权值typedef struct/定义图的结构VertexTYpe vexsMVNUM;/顶点数组，类型定义为char 型Adjmatrix arcsMVNUMMVNUM;/领接矩阵为int 型MGraph;int D1MVNUM,p1MVNUM;int DMVNUMMVNUM,pMVNUMMVNUM;/设置为全局变量，存放每对节点的路径和长度2、主程序的流程图： 图1流程图说明，首先开始程序输入边数和节点数，调用建图函数进行建图操作，对建好的图可以有选择进行矩阵的输出与否，再选择不同的Floyd算法来求 最短路径的可以有不同的输出形式，在结束每一种显示方法后，都可以返回到选择界面，直到选择3退出程序。三、详细设计和编码：我们可以从以下几个方面进行分析：1.弗罗伊德(Floyd)算法的基本思想如下： 对我们输入的有向网G=(V , E) i , jV 用邻接矩阵arcsij表示有向网。若 i 到 j 有一条弧，则存在arcsij 为从 i 到 j 的路径长度，但它不一定是从 i 到 j 的最短 路径长度。我们应依次考虑 i 到 j 能否有以顶点1、2、n 为中间结点的更短路径，这样进行不短的试探。1.1首先考虑从 i 到 j是否有以顶点 1 为中间结点的路径。 即：是否有、，若有，则比较arcsij 与arcsi1+ arcs1j较短者为当前所求得的最短路径。 此时应修正arcsij 的值，并记下 i 的后继1。此时arcsij 的值是从 i 到 j 、中间顶点数不大于 1 时的最短路径。1.2 其次，考虑从 i 到 j 是否有包含顶点 2 为中间点的路径。若无，则从 i 到 j 的最短路径是(1)步求得的；若有，则 i 2j 可分解为两条路径：i 2 、2j 这两条路径的最短路径是是在(1)步求得的，（即i 2 、2j可分别看作 (1)步中的 i 、j，它们之间有数量不超过 1 的结点）比较arcs1ij 与arcs1i2+ arcs12j ， 可修正arcs1ij 的值为arcs2ij （它是当前求得的从 i 到 j 、中间顶点数不大于 2 时的最短路径）。1.3 依次类推，直到考虑了顶点 n 加入当前从 i 到 j 的最短路径后，得出最新的最短路径arcsnij 是从 i 到 j 之间经过的顶点数不大于 n 时的最短路径长度现已考虑了所有顶点作为中间点的可能性，因而它必是从 i 到 j 的最短路径。由此看出，弗罗伊德(Floyd)算法实际是通过一系列矩阵D0 、 D1 、D2 Dn 、来实现求解。其中，Dkij 即arcsij ，表示从 i 到 j 之间经过的顶点数=k 时的最短路径长度。讨论的焦点： 由Dk-1 求Dk if (Dk-1ik +Dk-1kj Dkij) Dkij = Dk-1ik +Dk-1kj 算法描述如下： 设置矩阵Dn+1n+1 记录两点间的路径长度。 设置矩阵p n+1n+1 记录每一次求得当前两点 i 、j 间最短路径时，i 的后继顶点。算法结束时，由p ij的值可得从 i 到 j 的最短路径上的各个顶点。第一步： 初始化Dn+1n+1 ，使Dij=arcsij 初始化p n+1n+1 ，若从 i 到 j 有一条弧，则p ij j ,否则p ij 0 。第二步： 做 n 次迭代，每次均试图将顶点 k 扩充到当前求得的最短路径上，并修改 i 的后继顶点号。 for ( k=1; k=n; k+ ) for ( i =1; i =n; i + ) for (j =1; jDik+Dkj) Dij = Dik+Dkj ; p ij = p ik ; 2. 弗罗伊德(Floyd)算法主要描述如下： void Floyd(MGraph *G,int n)/Floyd算法 int i,j,k; for(i=1;i=n;i+)/设置路径长度D和路径P的初值 for(j=1;jarcsij!=Maxint)/判断两点间是否有直接路径，有就将它的权值赋给Pij pij=j; else pij=0;/否则将它赋为0 Dij=G-arcsij; for(k=1;k=n;k+)/查找他们之间是否有中间节点 for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+Dkj2,2-3但对于要求输入1-3的最短路径时，系统给出没有路径。在对Floyd函数进行仔细的查看和分析，了解到是因为循环没有做好控制，加以修改就解决了问题。2.该开始没有对输入的节点的起点和终点的的范围加以控制，系统不提示，但在矩阵输出时，就不会输出超过范围的点的信息。加了一do()while循环就可以提示，还可以对错误的输入进行再次的输入。3.在显示最短路径的时候,同样出现了显示路径时对于1-2,23,的情况显示为1-3，而不是1-2-3，查看了是因为循环的空吃问题。加以修改即可。4. 在显示矩阵时，开始没有作好格式的控制，输出不对齐，修改格式后有不小心加了一个空格，细心检查才发现了错误。5.在最后的选择case语句时，刚开始没有做返回到主控菜单，设计不全面，加了一个do()while循环控制就可以了。1.2算法的时、空性能分析：时间复杂度是：O（n3），空间复杂度是：O（n）1.3改进设想： 通过对程序测试的进一步的分析，我认为可以对它进行以下的改进：1.可以在程序中加入实现无向图的邻接矩阵，设置它们是等距的，这样就可以求无向图的两节点间的最短路径问题。2.可以预存入一组数据，假设为已经是一个已知地点的交通图，让用户可以直接查询不用输入建立有向图。2对设计实现的回顾讨论和分析：这是一个实现求图的最短路径算法的课题，所以需要先建立一个图来进行Floyd算法的运算。设计程序的时候，先是初步设计一些子函数：1. createMGaph()函数，用来输入数据构建有先向图的邻接矩阵表示；2. dispmgraph()函数，用来显示已建立的有向图用领接矩阵输出；3. Floyd()函数，用来求有向图的最短路径。4. Floyd1()函数，在4的基础上输出所有节点的最短路径。5. main()主函数，主要做的是界面，用来提示用户的输入输出以及一些选择。五.用户使用说明：运行程序后可看到系统界面，提示用户输入他要查阅的图的情况，先输入图的节点数和边数，在输入每边的信息，包括起点，终点和权值。（超过范围会有提示）比如说节点数和边数为3和3输入为3 3（空格隔开），输入起点终点和权值同样是空格隔开；再来就是选择是否输出有向图的领接矩阵，用户输入y/n进行选择即可；之后是本设计的重点部分，用户可以通过1,2,3 选择不同的方法来求最短路径。1为求两个确定点的最短路径，用户需要输入要查询的起点和终，比如求1-3的最短路径，输入格式：1 3（有空格），就可查阅1-3的路径了。在用户查阅完之后，可以通过0 0结束查询。2为求所有节点的最短路径，选择后，系统会给出所有的节点之间的最短路径。选择三将退出整个系统。六、测试结果：1.1当输入3个顶点3条边1-2-3的路径长大于1-3的情况为：1.2当输入3个顶点3条边1-2-3的路径长小于1-3的情况为：2.结果分析：通过对程序的运行结果的分析，我们可以看到通过选择不同的求路径的方法所得到的最短路径长度是一样的，。由1.1和1.2的输出最短路径的不同就可以得到，。它所求的最短路径是所有通路中最短的一条。七参考资料： 1.严蔚敏等。数据结构题集（c语言）。北京：清华大学出版社，1999年2月第1版。2.李春葆。数据结构与算法教程。北京：清华大学出版社，2005年6月第1 版。3.苏仕华，数据结构课程设计,北京：机械工业出版社, 2005年5月第1版。八、源程序：#include#define MVNUM 100 /最大顶点个数#define Maxint 32767/用32767来表示无穷#include#include#include#includeenum boolean False,True;typedef char VertexTYpe;/定义顶点的值类型typedef int Adjmatrix;/定义顶点的权值typedef struct/定义图的结构VertexTYpe vexsMVNUM;/顶点数组，类型定义为char 型Adjmatrix arcsMVNUMMVNUM;/领接矩阵为int 型MGraph;int D1MVNUM,p1MVNUM;int DMVNUMMVNUM,pMVNUMMVNUM;/设置为全局变量，存放每对节点的路径和长度void createMGaph(MGraph *G, int n,int e)int i,j,k=1,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;cout输入e条边的顶点终点和权值(以空格隔开!):n|jn)/判断是否超出范围 printf(错识,重新输入n); else G-arcsij=w;/将权值赋给G-arcsij k+;while(kn;/e=G-e;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;jarcsij=Maxint)/若两点间无直接路径为 /if(i!=j)/printf( ); coutsetw(8); /else cout setw(8)0; else coutsetw(8)arcsij;/否则输出它的权值 coutendl;void Floyd(MGraph *G,int n)/Floyd算法 int i,j,k; for(i=1;i=n;i+)/设置路径长度D和路径P的初值 for(j=1;jarcsij!=Maxint)/判断两点间是否有直接路径，有就将它的权值赋给Pij pij=j; else pij=0;/否则将它赋为0 Dij=G-arcsij; for(k=1;k=n;k+)/查找他们之间是否有中间节点 for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+DkjDij)/判断中间节点的路径之和是否小于Dij小于就将中间节点的值赋给Pij Dij=Dik+Dkj; pij=k;void Floyd1(MGraph *G,int n)/Flyod算法 int i,j,k; for(i=1;i=n;i+)/设置路径长度D和路径P的初值 for(j=1;jarcsij; pij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+DkjDij) /判断中间节点的路径之和是否小于Dij小于就将中间节点的值赋给Pij Dij=Dik+Dkj; pij=k; for(i=1;i=n;i+)/循环控制输出所有的节点间的最短路径 for(j=1;j=n;j+) if(i!=j) cout ij:; if(Dij=Maxint) if(i!=j) cout不存在路径endl; else cout路径长度为：setw(3)Dij ; cout路径为：i; k=pij; while(k!=0) coutk; k=pkj; coutjendl; v