基于VC的最短路径Floyed算法的实现

课程设计说明书NO.1沈阳大学科技工程学院基于VC的最短路径Floyed算法的实现1.课程设计的目的为了巩固“通信网技术应用”课程学到的相关知识，通过对本课程所学知识的综合运用，融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。通过floyed算法求解图中顶点的最短路径问题实验，更加深入的了解了数据结构与算法在各个领域的应用。比如图的最短路径问题，衍生为校内导游图，乘车路径问题等等的实际性的日常问题。2.设计方案论证2.1Floyd算法定义Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。2.2核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);其状态转移方程如下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表示i到j的最短距离K是穷举i,j的断点map[n,n]初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理,比如没有map[i,k]这条路2.3算法过程把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，课程设计说明书NO.2沈阳大学科技工程学院比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Floyd算法。⑴通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。⑵深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。⑶在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。3.设计的过程与分析3.1设计的过程对于任意图，选择存储结构存储图并实现FLOYED算法求解最短路径。将问题分解，分解为两个方面。一是对于任意图的存储问题，第二个是实现floyed算法求解最短路径。首先对于图的创建选择合适的存储结构进行存储，对于合适的存储结构可以简化程序。本实验采用邻接矩阵存储。然后是实现FLOYED算法求解最短路径，在FLOYED算法中路径的长度即是图中两顶点间边的权值，FLOYED算法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出。考虑到问题的特殊性，采用两个二维数组进行存储。第一个二维数组存储最短路径，第二个二维数组存储路径经过的顶点，在进行适当的运算后对这两个数组进行输出即可。通过问题的分解，逐个解决，实现所要求程序。课程设计说明书NO.3沈阳大学科技工程学院为实现上述程序的功能，需要创建邻接矩阵存储图，FLOYED算法求解最短路径。在求解最短路径的时候需要申请两个二维数组A[][]和path[][]分别存储路径和路径经过的顶点。输出是需判断A[][]的值，若A[i][j]=0但i!=j,此时i到j的路径长度就是0，若A[i][j]=INF,及最大值，表示从i到j没有路径，输出路径的同时输出经过的顶点即可。本程序包含个函数(1)主函数main()(2)邻接矩阵创建函数create()(3)FLOYED算法函数floyed()(4)输出函数dispath()(5)前递归输出函数ppath()各函数间关系如下：图1主函数及个函数间关系对于任意图，选择存储结构存储图并实现FLOYED算法求解最短路径。由课程设计题目，设计思想如下：对于图，可采用邻接矩阵和邻接表存储，本程序采用邻接矩阵存储。maincreatdispathfloydeppath课程设计说明书NO.4沈阳大学科技工程学院假设G={V,E}是一个有n个顶点的图，我们规定个顶点的序号依次为1，2，3，……，n,则G的邻接矩阵是一个具有如下定义的n阶方阵：A[i,j]=1,若Vi,Vj或者（Vi,Vj）∈E(G)A[i,j]=0，反之对于在边上附有权值的网，可以将以上的定义修正为：A[i,j]=Wi,若Vi,Vj或者（Vi,Vj）∈E(G)A[i,j]=0,反之其中Wi表示Vi,Vj弧或者（Vi,Vj）边上的权值。一个图的邻接矩阵存储结构可以用两个数组来表示。其中第一个数组vexs是一维数组，用来存储途中顶点的信息；另外一个二维数组edges，用来存储途中边或者弧的信息。邻接矩阵数据类型如下：typedefstruct{intdata;//顶点信息intnum;//顶点序号}vertex;typedefstruct{intn;//顶点个数inte;//边个数vertexvexs[ma];//存储顶点intedges[ma][ma];//存储边的权值}mgraph;//邻接矩阵存储图在图的初始化过程中，若两顶点无直接路径的话，就用自定义最大变量INF9999来表示。如上就解决了图的存储问题。下面就FLOYED算法求解最短路径给出设计思想如下：如果有一个矩阵D=[A(ij)]，其中A(i，j)表示i顶点到j顶点的距离。若i与j之间无路可通，那么A(i，j)就是无穷大，本程序用自定义的一个最大数9999表示。又有A(i，i)=0，若i=j，则是顶点，无需考虑，若i!=j,则表示这两点间的路径长度为0.编写一个程序，通过这个距离矩阵D，把任意两个点之间的最短与其行径的路径找出来。课程设计说明书NO.5沈阳大学科技工程学院我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里用到动态规划的知识，对于任何一个点而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是点的数目)，在检查A(i,j)与A(i,k)+A(k,j)的值；在此A(i,k)与A(k,j)分别是目前为止所知道的i到k与k到j的最短距离，因此A(i,k)+A(k,j)就是i到j经过k的最短距离。所以，若有A(i,j)A(i,k)+A(k,j)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，这样把i到j的A(i,j)通过赋值运算A(i,j)=A(i,k)+A(k,j)，每当一个k查完了，A(i,j)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，A(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题完成：for(k=1;k=g-n;k++)for(i=1;i=g-n;i++)for(j=1;j=g-n;j++)就是如何找出最短路径所经过的点，这里要用到另一个矩阵path，它的定义是这样的：path(i，j)的值如果为p，就表示i到j的最短行经为i-...-p-j，也就是说p是i到j的最短行径中的j之前的最后一个点。path矩阵的初值为path(i,j)=-1。对于i到j而言找出path(i,j)，令为p，就知道了路径i-...-p-j；再去找path(i,p)，如果值为q，i到p的最短路径为i-...-q-p；再去找path(i,q)，如果值为r，i到q的最短路径为i-...-r-q-p；所以一再反复，到了某个path(i,t)的值为-1时，就表示i到t的最短路径为i-t，即是到终点，则i到j的最短行径为i-t-...-q-p-j。因为上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。利用向前递归的算法实现，思想如下：voidppath(intpath[][ma],inti,intj){//向前递归查找路径上的顶点intk;k=path[i][j];if(k==-1)return;ppath(path,i,k);printf(%d-,k);课程设计说明书NO.6沈阳大学科技工程学院ppath(path,k,j);}所经过的点如何保存问题，解决思想如下：在判断最短路径的时候，如过当前的路径比经过某几个顶点后的路径要长的话，对当前的路径进行修改，并保存下经过的顶点，用矩阵path来存储。实现如下：for(k=1;k=g-n;k++){for(i=1;i=g-n;i++)for(j=1;j=g-n;j++)if(A[i][k]!=0&&A[k][j]!=0&&A[i][j](A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}输出最短路径可调用输出函数来实现，本程序中用dispath函数来实现输出模块。voiddispath(intA[][ma],intpath[][ma],intn)//输出所有顶点最短路径{inti,j;for(i=1;i=n;i++)for(j=1;j=n;j++)if(A[i][j]==INF){if(i!=j)printf(从%d到%d没有路径\n,i,j);}elseif(A[i][j]==0){if(i!=j){printf(从%d到%d的最短路径为:,i,j);printf(%d-,i);ppath(path,i,j);printf(%d,j);printf(\t路径长度为:%d\n,A[i][j]);}}else{printf(从%d到%d的最短路径为:,i,j);课程设计说明书NO.7沈阳大学科技工程学院printf(%d-,i);ppath(path,i,j);printf(%d,j);printf(\t路径长度为:%d\n,A[i][j]);}}在输出模块调用前递归查找函数，输出经过的顶点。如上就实现了本程序要求的所用功能，对于任意图采用存储结构存储，并实现FLOYED算法求解最短路径。3.1设计结果与分析程序名为floyef.c，运行环境为DOS。程序执行后显示初始化图，请输入顶点个数和边的个数：输入412输入顶点信息，顶点序号：输入1234输入边的信息，权值，相邻顶点有边，若不连接权值为9999表1有向表起始点终结点权值1216131514999921292399992413312132999934741999942274319课程设计说明书NO.8沈阳大学科技工程学院图2有