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

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

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

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

3、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的最短路径，则

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

5、中间顶点序号不大于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])//弗洛伊德算法{inti,j,k,next;for(i=0;i〈n;i++)for(j=

6、O;j

7、）//输山{for（j=0;j%d无可达路径",i+1,j+1）;//printfrrT）;}else{printf（〃％d〃，i+1）;while（q!=j+1）{printf（"—〉％d",q）;//printf（"%d〃，a[i+l][q]）;q=path[q-l][j];}printf（〃一>%d，z,j+1）;}三、结论1、实验结果**

8、***输出任意两点间的最短距离和经过路径如下*™01