实验三-最短路径算法分析与设计

学 生 实 验 报 告学 院： 软件与通信工程学院 课程名称： 算法分析与设计 专业班级： 软件144班 姓 名： 刘洋 学 号： 0144119 学生实验报告学生姓名刘洋学号0144119同组人实验项目最短路径算法分析与设计必修 选修 演示性实验 验证性实验 操作性实验 综合性实验实验地点G108实验仪器台号指导教师李刚实验日期及节次4-89A一、实验综述1、实验目的及要求目的：（1）熟悉不同最短路径问题的求解的方法与一般技巧；（2）掌握Floyd算法、Dijkstra算法的实现；（3）掌握调试、改进算法程序基本方法；（4）熟悉两种方法在解决问题中的应用；要求：（1）自己生成问题实例；（2）报告不同算法在实验中的表现。2、实验仪器、设备或软件仪器：Windows xp/7/8/10软件：vs2013二、实验过程（实验步骤、记录、数据、分析）问题实例：利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。算法设计思想：弗洛伊德算法是用邻接矩阵cost表示带权有向图。如果从顶点Vi到Vj有弧，则从到Vj存在一条长度为costij的路径，该路径不一定是最短路径，需要进行n次试探。首先考虑路径（Vi，V1，Vj）是否存在（即判别弧（vi，v1）（v1，vj）是否存在），如果存在，则比较（Vi，V1，Vj）和（vi，vj）的路径长度，取较短者为从vi到vj的中间顶点序号不大于1的最短路径、在路径上再增加一个顶点v2，若（vi ,v2）和（v2 vj）分别是当前找到的中间顶点序号不大于1的最短路径，则（vi.,v2,vj）就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将他和已经得到从vi到vj中间顶点序号不大于1的最短路径比较，从中选出长度较短者作为从vi到vj中间顶点序号不大于2的最短路径之后，再增加一个顶点v3，继续进行试探，依次类推。在一般情况下，若（vi ,vk）和（vk vj）分别是从vi到vk和vk到vj的中间顶点序号不大于k-1的最短路径，则将（vi , vk vj）和已经得到的vi到vj且中间顶点序号不大于k-1的最短路径相比较，取其长度较短者作为从vi到vj的中间顶点序号不大于k的最短路径。如此重复，经过n次比较，最后求的的必是从vi到vj的最短路径。用此方法，课可同时求的每对顶点间的最短路径。 综上所述，佛洛依德算法的基本思想是递推的产生一个矩阵序列：a0,a1,akan,其中：a0ij=costij;Akij=mina(k-1)ij,a(k-1)ik+a(k-1)jk;(1<=k<=n);由上述公式可以看出，aij是从Vi到Vj中间顶点序号不大于1的最短路径长度；akij是从Vi到Vj中间顶点序号不大于1的最短路径长度；anij是从Vi到Vj的最短路径长度。还设置一个矩阵path,pathij是从Vi到Vj中间顶点序号不大于k的最短路径上Vi的一个邻接顶点的序号，约定Vi到Vj无路径时pathij=0;由pathij的值，可以得到从Vi到Vj最短路径。实验源码：void floyd(int an,int costnn,int pathn)/弗洛伊德算法int i,j,k,next;for( i=0;i<n;i+)for( j=0;j<n;j+)if(costij<L)pathij=j+1;else pathij=0;aij=costij;for( k=0;k<n;k+)/以下三个循环是用于进行路径最短的查找与输出for(i=0;i<n;i+)for(j=0;j<n;j+)if(aij>aik+akj)aij=aik+akj;pathij=pathik; int q; printf("n*输出任意两点间的最短距离和经过路径如下*nn"); for(i=0;i<n;i+)/输出for(j=0;j<n;j+)printf(" 最短距离: %d ",aij);/printf("请输入起点n"); / scanf("%d",q);q=pathij;if(q=0)printf("%d->%d无可达路径n",i+1,j+1);/printf("n");elseprintf(" %d",i+1);while(q!=j+1)printf("->%d",q);/printf(" %d ",ai+1q);q=pathq-1j;printf("->%dn",j+1); 三、结论1、实验结果2、分析讨论从实验结果可以看出这个算法程序是一个只能够直接输出两点间的最短路径，而不能从键盘输入起点与终点，就这一点对于实际生活中就有点冗余，因此还有待改进。四、指导教师评语及成绩：评语：成绩： 指导教师签名： 批阅日期：