最短路的Floyd算法ppt课件.ppt_第1页
最短路的Floyd算法ppt课件.ppt_第2页
最短路的Floyd算法ppt课件.ppt_第3页
最短路的Floyd算法ppt课件.ppt_第4页
最短路的Floyd算法ppt课件.ppt_第5页
已阅读5页，还剩12页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

运筹学 讲课教师 1 4 3 3最短路的Floyd算法 FLOYD算法以上介绍的算法用来求源点至各点的最短路 在有些问题中 我们需要知道节点两两之间的最短路 比如选址问题 这类问题可以用DIJKSTRA算法 依次改变源点来求解 但计算比较繁琐 现在介绍一种直接计算任意两节点之间最短路的方法 Floyd算法 该算法由Floyd于1962年提出 2 4 3 3最短路的Floyd算法 Floyd算法是权矩阵迭代算法 记网络的权矩阵为 其中 3 4 3 3最短路的Floyd算法 算法基本步骤为 2 计算 其中 3 重复 2 直到 此时 即为节点i到点j的最短路的距离 1 令 4 4 3 3最短路的Floyd算法 例4 3 4用Floyd算法计算图4 21中任意两节点间的最短路 5 4 3 3最短路的Floyd算法 解 写出图4 21的权矩阵D 并令 6 4 3 3最短路的Floyd算法 7 4 3 3最短路的Floyd算法 D1的元素d1ij的意义为i直接到达j及经节点1到达j的两种方式中 最短路线的距离 8 4 3 3最短路的Floyd算法 9 4 3 3最短路的Floyd算法 D2的元素d2ij的意义为i直接到达j及最多经节点1 2到达j的所有方式中 最短路线的距离 这些可能的方式有 i j i 1 j i 2 j i 1 2 j i 2 1 j 例如d243 4423表示节点4到节点3在这些方式中取4 2 3为最短路 距离为4 下标 423 便于在算法结束时确定最短路之用 10 4 3 3最短路的Floyd算法 11 4 3 3最短路的Floyd算法 12 4 3 3最短路的Floyd算法 任意两节点之间的最短路 最多可经过节点1 2 n到达 因此当计算到Dn时 算法已结束 至此 得到任意两点间的最短路及其距离 如本例题中 节点1 6之间的最短路为1 2 4 6 距离为9 节点3 4之间的最短路为3 5 4 距离为3 节点6 4之间的最短路为6 4 距离为3 等等 13 4 3 3最短路的Floyd算法 例4 3 5选址问题 最短路问题的应用II图4 22为某地区的居民区分布图 各边旁的数据为居民区间的距离 拟在其中一个居民区建一个大型超市 问超市建在那里 才能使距离超市最远的居民到超市的距离最近 14 4 3 3最短路的Floyd算法 解 如果超市建在i点 则需计算出i至各点的最短路的距离 其中最大者即离超市最远 于是问题变成求这些最大最短路中的最小者 15 4 3 3最短路的Floyd算法 为此需计算任意两点间的最短路 表示节点i到各节点的最短路中的最大值 超市应建在第6居民区 到超市最远的居民区为节点5所示的小区 距离为4
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论