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

1、基于VC的最短路径Floyed算法的实现1.课程设计的目的为了巩固“通信网技术应用”课程学到的相关知识，通过对本课程所学知识的综合运用，融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。通过floyed算法求解图中顶点的最短路径问题实验，更加深入的了解了数据结构与算法在各个领域的应用。比如图的最短路径问题，衍生为校内导游图，乘车路径问题等等的实际性的日常问题。2.设计方案论证2.1 Floyd算法定义Floyd算法又称为弗洛伊德算法，插点法，是一种用

2、于寻找给定的加权图中顶点间最短路径的算法。2.2核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行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(n3); 其状态转移方程如下： mapi,j:=m

3、inmapi,k+mapk,j,mapi,j mapi,j表示i到j的最短距离 K是穷举i,j的断点 mapn,n初值应该为0，或者按照题目意思来做。 当然，如果这条路没有通的话，还必须特殊处理,比如没有mapi,k这条路 2.3算法过程把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=空值。 定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。 把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。 在G中

4、包含有两点之间最短道路的信息，而在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) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由

5、D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Floyd算法。 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。 在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。3.设计的过程与分析3.1设计的过程对于任

6、意图，选择存储结构存储图并实现FLOYED算法求解最短路径。将问题分解，分解为两个方面。一是对于任意图的存储问题，第二个是实现floyed算法求解最短路径。首先对于图的创建选择合适的存储结构进行存储，对于合适的存储结构可以简化程序。本实验采用邻接矩阵存储。然后是实现FLOYED算法求解最短路径，在FLOYED算法中路径的长度即是图中两顶点间边的权值，FLOYED算法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出。考虑到问题的特殊性，采用两个二维数组进行存储。第一个二维数组存储最短路径，第二个二维数组存储路径经过的顶点，在进行适当的运算后对这两个数组进行输出即可。通过问题的分解，逐个解

7、决，实现所要求程序。为实现上述程序的功能，需要创建邻接矩阵存储图，FLOYED算法求解最短路径。在求解最短路径的时候需要申请两个二维数组A和path分别存储路径和路径经过的顶点。输出是需判断A的值，若Aij=0但i!=j,此时i到j的路径长度就是0，若Aij=INF,及最大值，表示从i到j没有路径，输出路径的同时输出经过的顶点即可。本程序包含个函数(1)主函数main()(2)邻接矩阵创建函数create()(3)FLOYED算法函数floyed()(4)输出函数dispath()(5)前递归输出函数ppath()各函数间关系如下：maincreatdispathfloydeppath图1主函

8、数及个函数间关系对于任意图，选择存储结构存储图并实现FLOYED算法求解最短路径。由课程设计题目，设计思想如下：对于图，可采用邻接矩阵和邻接表存储，本程序采用邻接矩阵存储。假设G=V,E是一个有n个顶点的图，我们规定个顶点的序号依次为1，2，3，n,则G的邻接矩阵是一个具有如下定义的n阶方阵：Ai,j=1,若或者（Vi,Vj）E(G)Ai,j=0，反之对于在边上附有权值的网，可以将以上的定义修正为： Ai,j=Wi, 若或者（Vi,Vj）E(G)Ai,j=0, 反之其中Wi表示弧或者（Vi,Vj）边上的权值。一个图的邻接矩阵存储结构可以用两个数组来表示。其中第一个数组vexs是一维数组，用来存

9、储途中顶点的信息；另外一个二维数组edges，用来存储途中边或者弧的信息。邻接矩阵数据类型如下：typedef structint data;/顶点信息int num;/顶点序号vertex;typedef structint n;/顶点个数int e;/边个数vertex vexsma;/存储顶点int edgesmama;/存储边的权值mgraph;/邻接矩阵存储图在图的初始化过程中，若两顶点无直接路径的话，就用自定义最大变量INF9999来表示。如上就解决了图的存储问题。下面就FLOYED算法求解最短路径给出设计思想如下：如果有一个矩阵D=A(ij)，其中A(i，j)表示i顶点到j顶点的

10、距离。若i与j之间无路可通，那么A(i，j)就是无穷大，本程序用自定义的一个最大数9999表示。又有A(i，i)=0，若i=j，则是顶点，无需考虑，若i!=j,则表示这两点间的路径长度为0. 编写一个程序，通过这个距离矩阵D，把任意两个点之间的最短与其行径的路径找出来。我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里用到动态规划的知识，对于任何一个点而言，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

11、)分别是目前为止所知道的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; kn; k+) for(i=1; in; i+) for(j=1; jn; j+)就是如何找出最短路

12、径所经过的点，这里要用到另一个矩阵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。因为

13、上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。利用向前递归的算法实现，思想如下：void ppath(int pathma, int i, int j)/向前递归查找路径上的顶点int k;k=pathij;if(k=-1)return; ppath(path,i,k);printf(%d-,k);ppath(path,k,j); 所经过的点如何保存问题，解决思想如下：在判断最短路径的时候，如过当前的路径比经过某几个顶点后的路径要长的话，对当前的路径进行修改，并保存下经过的顶点，用矩阵path来存储。实现如下：for(k=1; kn; k+)for(i=1; in; i+

14、)for(j=1; jn; j+)if(Aik!=0 & Akj!=0&Aij(Aik+Akj)Aij=Aik+Akj;pathij=k;输出最短路径可调用输出函数来实现，本程序中用dispath函数来实现输出模块。void dispath(int Ama,int pathma,int n)/输出所有顶点最短路径int i,j;for(i=1; i=n; i+)for(j=1; j,i);ppath(path,i,j);printf(%d,j);printf(t路径长度为:%dn,Aij);elseprintf(从%d到%d的最短路径为:,i,j);printf(%d-,i);ppath(pa

15、th,i,j);printf(%d,j);printf(t路径长度为:%dn,Aij);在输出模块调用前递归查找函数，输出经过的顶点。如上就实现了本程序要求的所用功能，对于任意图采用存储结构存储，并实现FLOYED算法求解最短路径。3.1设计结果与分析程序名为floyef.c，运行环境为DOS。程序执行后显示初始化图，请输入顶点个数和边的个数：输入4 12输入顶点信息，顶点序号：输入1 2 3 4输入边的信息，权值，相邻顶点有边，若不连接权值为9999表1 有向表起始点终结点权值1216131514999921292399992413312132999934741999942274319123

16、4162913192127715图2 有向图程序运行输出得到的邻接矩阵如下所示：0 16 15 999929 0 9999 1321 9999 0 7 9999 27 19 0输出最短路径：从1到2的最短路径为：1-2 路径长度为：16从1到3的最短路径为：1-3 路径长度为：15从1到4的最短路径为：1-3-4 路径长度为：22从2到1的最短路径为：2-1 路径长度为：29从2到3的最短路径为：2-4-3 路径长度为：32从2到4的最短路径为：2-4 路径长度为：13从3到1的最短路径为：3-1 路径长度为：21从3到2的最短路径为：3-4-2 路径长度为：34从3到4的最短路径为：3-4

17、路径长度为：7从4到1的最短路径为：4-3-1 路径长度为：40从4到2的最短路径为：4-2 路径长度为：27从4到3的最短路径为：4-3 路径长度为：19无向图floyed算法求最短路径如下：124310347图3无向图 图中双向箭头表示该两点不直接连接。权值用最大值9999表示：图4 运行结果图如上就实现了本程序要求的所用功能，对于任意图采用存储结构存储，并实现FLOYED算法求解最短路径。3.2结论首先考虑的是对于任意图的存储问题。在数据结构与算法中，介绍了多种图的存储结构，有邻接矩阵存储，邻接表存储以及十字链表等等存储方法。考虑到本实验要对图进行求解路径，采用邻接矩阵存储。邻接矩阵存储

18、图很容易判断图中两个顶点是否相连。然后是路径问题。对于任意两个顶点，路径也就分为三种情况，即直接相连是最短路径，经过某几个顶点后，经过的路径是最短路径，还有这两个顶点之间没有最短路径。对于直接相连的路径就是最短路径，直接输出即可。最后待解决的问题就是输出任意两点之间的最短路径。 4设计体会通过为期一周的课程设计，使我对Floyd算法有了初步的了解， 本次课程设计涉及到的范围很广，让我能够比较系统的对C语言和数据结构进行一次整理和复习。又一次复习了C语言，在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用VC+的编译环境，在编写程序过程中要灵活应用。对数据结构的理解有待加强，这次课程设计应

19、用的算法是Floyed算法。在学习的过程中自己就对这方面的知识比较生疏，此次课程设计时间虽短，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远一个影响。总之，这次课程设计让我收获了很多，不仅对VC的基本运算有了初步的认识，还对Floyed算法有了更深刻的认识和理解，我相信，努力过了总会有收获的。5参考文献1 王昆仑，李红. 数据结构与算法M.北京：中国铁道出版社，2006.52 侯风巍，杨永田.数据结构要点精析M北京：航空航天大学出版社，20

20、06.83 李春葆，数据结构教程上机实验指导M.北京：清华大学出版社4 严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学出版社，2009.75 张福炎，程序员 高级程序员 程序设计及（第二版）M.北京：清华大学出版社，2008.6 6 黄刘生，唐策善：数据结构第二版M.中国科学技术大学出版社,2008.87刘腾红，孙细明.数据结构分析与设计M.北京：科学出版社，2003.5源代码/对于任意图，选择合适的数据结构存储，并实现求解最短路径的Floyd算法#include#include#define ma 100#define Null 0#define INF 9999typedef st

21、ructint data;/顶点信息int num;/顶点序号vertex;typedef structint n;/顶点个数int e;/边个数vertex vexsma;/存储顶点int edgesmama;/存储边的权值mgraph;/邻接矩阵存储图mgraph *create()/创建临界矩阵存储图int i,j,k,n,e,w; int c;mgraph g,*mg=&g;printf(初始化图，输入顶点数及边数);scanf(%d%d,&n,&e); mg-n=n;mg-e=e;printf(输入顶点信息，顶点序号n);for(i=1;ivexsi.data=c;mg-vexsi.num=i;for(i=1;i=n;i+)for(j=1;jedgesij=0;printf(输入边的信息，权值，相邻顶点有边，不连接权值为9999n);for(i=1;iedgesjk=w; printf(得到邻接矩阵如下：n); for(i=1;i=n