Floyd算法及其软件实现课件.ppt
《Floyd算法及其软件实现课件.ppt》由会员分享,可在线阅读,更多相关《Floyd算法及其软件实现课件.ppt(25页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、任意两点间的最短路问题Floyd算法z使用范围:1)求每求每对顶点的最短路径点的最短路径;2)有向有向图、无向、无向图和混合和混合图;z算法思想:直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2),D(v),D(v)是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径.z输入参数:G的带权邻接矩阵W.z算法输出:距离矩阵D以及路由矩阵R.1(I I)求距离矩阵的方法)求距离矩阵的方法)求距离矩阵的方法)求距离矩阵的方法.2(II)求路径矩阵的方法)求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R (III)查找最短路
2、路径的方法)查找最短路路径的方法.然后用同样的方法再分头查找若:然后用同样的方法再分头查找若:(IV)Floyd算法:求任意两顶点间的最短路算法:求任意两顶点间的最短路.例例3:求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径.6插入点插入点 v1,得:得:矩矩阵中中带“=”的的项为经迭代比迭代比较以后有以后有变化的元素化的元素.7插入点插入点 v2,得:得:矩矩阵中中带“=”的的项为经迭代比迭代比较以后有以后有变化的元素化的元素.8插入点插入点 v3,得:得:插入点插入点 v4,得:得:插入点插入点 v5,得:得:10插入点插入点 v6,得:得:11故从故从v5到
3、到v2的最短路的最短路为8 由由v6向向v5追溯追溯:由由v6向向v2追溯追溯:所以从到的最短路径所以从到的最短路径为:12选址问题选址问题1、中心问题、中心问题所所谓中心中心选址址问题就是在一网就是在一网络中中选择一点,一点,建立建立公用服公用服务设施施,为该网网络中的点提供服中的点提供服务,使得服,使得服务效率最高。比如一个区域的消效率最高。比如一个区域的消防站、自来水厂、学校、防站、自来水厂、学校、变电站、站、银行、商行、商店等店等选址。址。为了提高服了提高服务效率,自然的想法效率,自然的想法是将是将这些些设施建立在中心地点。要求施建立在中心地点。要求网网络中中最最远的被服的被服务点离服
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Floyd 算法 及其 软件 实现 课件
限制150内