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

.基于VC的最短路径Floyed算法的实现1.课程设计的目的为了稳固“通信网技术应用〞课程学到的相关知识，通过对本课程所学知识的综合运用，融会贯穿课程中所学的理论知识，初步掌握通信网络的体系构造和扩频通信系统等相关知识；加深对通信网络的根本理论、根本知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力通过floyed算法求解图中顶点的最短路径问题实验，更加深入的了解了数据构造与算法在各个领域的应用比方图的最短路径问题，衍生为校内导游图，乘车路径问题等等的实际性的日常问题2.设计方案论证2.1 Floyd算法定义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 把各个顶点插入图中，比拟插点后的距离与原来的距离，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算法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出考虑到问题的特殊性，采用两个二维数组进展存储第一个二维数组存储最短路径，第二个二维数组存储路径经过的顶点，在进展适当的运算后对这两个数组进展输出即可通过问题的分解，逐个解决，实现所要求程序为实现上述程序的功能，需要创立邻接矩阵存储图，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()各函数间关系如下：maincreatdispathfloydeppath图1主函数及个函数间关系对于任意图，选择存储构造存储图并实现FLOYED算法求解最短路径由课程设计题目，设计思想如下：对于图，可采用邻接矩阵和邻接表存储，本程序采用邻接矩阵存储假设G={V,E}是一个有n个顶点的图，我们规定个顶点的序号依次为1，2，3，……，n,那么G的邻接矩阵是一个具有如下定义的n阶方阵：A[i,j]=1,假设或者〔Vi,Vj〕∈E(G)A[i,j]=0，反之对于在边上附有权值的网，可以将以上的定义修正为： A[i,j]=Wi, 假设或者〔Vi,Vj〕∈E(G)A[i,j]=0, 反之其中Wi表示弧或者〔Vi,Vj〕边上的权值一个图的邻接矩阵存储构造可以用两个数组来表示其中第一个数组vexs是一维数组，用来存储途中顶点的信息；另外一个二维数组edges，用来存储途中边或者弧的信息。

邻接矩阵数据类型如下：typedef struct{ int data;//顶点信息 int num;//顶点序号}vertex;typedef struct{ int n;//顶点个数 int e;//边个数 vertex vexs[ma];//存储顶点 int edges[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，把任意两个点之间的最短与其行径的路径找出来我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线如何找出最短路径呢，这里用到动态规划的知识，对于任何一个点而言，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。

因为上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来利用向前递归的算法实现，思想如下：void ppath(int path[][ma], int i, int j){//向前递归查找路径上的顶点 int k; k=path[i][j]; if(k==-1) return; ppath(path,i,k); printf("%d->",k); 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函数来实现输出模块。

void dispath(int A[][ma],int path[][ma],int n)//输出所有顶点最短路径{ int i,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);} else if(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的最短路径为:"。