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

《实验三-最短路径算法分析与设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学生实验报告学院：软件与通信工程学院课程名称：算法分析与设计专业班级：软件144班姓名：刘洋学号：学生实验报告学生姓名刘洋学号同组人实验项目最短路径算法分析与设计□必修□选修□演示性实验□验证性实验□操作性实验□综合性实验实验地点G108实验仪器台号指导教师李刚实验日期及节次4-89A一、实验综述1、实验目的及要求目的：（1）熟悉不同最短路径问题的求解的方法与一般技巧；（2）掌握Floyd算法、Dijkstra算法的实现；（3）掌握调试、改进算法程序基本方法；（4）熟悉两种方法在解决问题中的应用；要求：（1）自己生成问题实例；（2）报

2、告不同算法在实验中的表现。2、实验仪器、设备或软件仪器：Windowsxp/7/8/10软件：vs2013二、实验过程（实验步骤、记录、数据、分析）问题实例：利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。算法设计思想：弗洛伊德算法是用邻接矩阵cost表示带权有向图。如果从顶点Vi到Vj有弧，则从到Vj存在一条长度为cost[i][j]的路径，该路径不一定是最短路径，需要进行n次试探。首先考虑路径（Vi，V1，Vj）是否存在（即判别弧（vi，v1）（v1，vj）是否存在），如果存在，则比较（Vi，V1，Vj）和

3、（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的中间顶

4、点序号不大于k-1的最短路径，则将（vi…,vk…vj）和已经得到的vi到vj且中间顶点序号不大于k-1的最短路径相比较，取其长度较短者作为从vi到vj的中间顶点序号不大于k的最短路径。如此重复，经过n次比较，最后求的的必是从vi到vj的最短路径。用此方法，课可同时求的每对顶点间的最短路径。综上所述，佛洛依德算法的基本思想是递推的产生一个矩阵序列：a0,a1,…ak…an,其中：a0[i][j]=cost[i][j];Ak[i][j]=min{a(k-1)[i][j],a(k-1)[i][k]+a(k-1)[j][k];}(1<=k<

5、=n);由上述公式可以看出，a[i][j]是从Vi到Vj中间顶点序号不大于1的最短路径长度；ak[i][j]是从Vi到Vj中间顶点序号不大于1的最短路径长度；an[i][j]是从Vi到Vj的最短路径长度。还设置一个矩阵path,path[i][j]是从Vi到Vj中间顶点序号不大于k的最短路径上Vi的一个邻接顶点的序号，约定Vi到Vj无路径时path[i][j]=0;由path[i][j]的值，可以得到从Vi到Vj最短路径。实验源码：voidfloyd(inta[][n],intcost[n][n],intpath[][n])//弗洛伊

6、德算法{inti,j,k,next;for(i=0;ia[i][k]+a[k][j]){a[i][j]=a[i][k]+a[k][j];path[i][j]=path[i][

7、k];}}}}intq;printf("*****输出任意两点间的最短距离和经过路径如下*****");for(i=0;i%d无可达路径",i+1,j+1);//printf("");}else{printf("%d",i+1);while(q!=j+1){printf

8、("-->%d",q);//printf("%d",a[i+1][q]);q=path[q-1][j];}printf("-->%d",j+1);}}}三、结论1、实验结果2、分析讨论从实验结果可以看出这个算法程序是