实验三 最短路径算法分析与设计(5页).doc
《实验三 最短路径算法分析与设计(5页).doc》由会员分享,可在线阅读,更多相关《实验三 最短路径算法分析与设计(5页).doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、-实验三 最短路径算法分析与设计-第 5 页学 生 实 验 报 告学 院: 软件与通信工程学院 课程名称: 算法分析与设计 专业班级: 软件144班 姓 名: 刘洋 学 号: 0144119 学生实验报告学生姓名刘洋学号0144119同组人实验项目最短路径算法分析与设计必修 选修 演示性实验 验证性实验 操作性实验 综合性实验实验地点G108实验仪器台号指导教师李刚实验日期及节次4-89A一、实验综述1、实验目的及要求目的:(1)熟悉不同最短路径问题的求解的方法与一般技巧;(2)掌握Floyd算法、Dijkstra算法的实现;(3)掌握调试、改进算法程序基本方法;(4)熟悉两种方法在解决问题中
2、的应用;要求:(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)的路径
3、长度,取较短者为从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且中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验三 最短路径算法分析与设计5页 实验 路径 算法 分析 设计
限制150内