Floyd算法及其软件实现PPT.ppt

任意两点间的最短路问题Floyd算法z使用范围:1)求每求每对顶点的最短路径点的最短路径;2)有向有向图、无向、无向图和混合和混合图;z算法思想:直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2),D(v),D(v)是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径.z输入参数：G的带权邻接矩阵W.z算法输出：距离矩阵D以及路由矩阵R.12024/11/2 周六（I I）求距离矩阵的方法）求距离矩阵的方法）求距离矩阵的方法）求距离矩阵的方法.22024/11/2 周六（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R （III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.例例3：求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径.62024/11/2 周六插入点插入点 v1，得：得：矩矩阵中中带“=”的的项为经迭代比迭代比较以后有以后有变化的元素化的元素.72024/11/2 周六插入点插入点 v2，得：得：矩矩阵中中带“=”的的项为经迭代比迭代比较以后有以后有变化的元素化的元素.82024/11/2 周六插入点插入点 v3，得：得：插入点插入点 v4，得：得：插入点插入点 v5，得：得：102024/11/2 周六插入点插入点 v6，得：得：112024/11/2 周六故从故从v5到到v2的最短路的最短路为8 由由v6向向v5追溯追溯:由由v6向向v2追溯追溯:所以从到的最短路径所以从到的最短路径为：122024/11/2 周六选址问题选址问题1、中心问题、中心问题所所谓中心中心选址址问题就是在一网就是在一网络中中选择一点，一点，建立建立公用服公用服务设施施，为该网网络中的点提供服中的点提供服务，使得服，使得服务效率最高。比如一个区域的消效率最高。比如一个区域的消防站、自来水厂、学校、防站、自来水厂、学校、变电站、站、银行、商行、商店等店等选址。址。为了提高服了提高服务效率，自然的想法效率，自然的想法是将是将这些些设施建立在中心地点。要求施建立在中心地点。要求网网络中中最最远的被服的被服务点离服点离服务设施的距离尽可能小施的距离尽可能小。132024/11/2 周六设网网络N有个有个n点点v1,v2,vn。dij表示点表示点vi到到vj之之间的距的距离（即最短路的离（即最短路的长度），并度），并记dii=0(i=1,2,n)。定义定义1:记 ,。若。若 ,则称点称点vk为网网络N的中心，的中心，I为直径。直径。定义定义2:令令 ，若，若 ，则称称vk为网网络N的中心。的中心。142024/11/2 周六例例1某城市要建立一个消防站，为该市所某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在哪个属的七个区服务，如图所示问应设在哪个区，才能使它至最远区的路径最区，才能使它至最远区的路径最 短。短。152024/11/2 周六S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.162024/11/2 周六例例2 教教育育部部门门打打算算在在某某新新建建城城区区建建一一所所学学校校，让让附附近近七七个个居居民民区区的的学学生生就就近近入入学学。七七个个居居民民区区之之间间的的道道路路如如下下图图所所示示，学学校校应应建建在在哪哪个个居居民民区区，才才能能使使大大家家都都方方便便？（图图中中距距离离单单位位：百米）。百米）。172024/11/2 周六18192024/11/2 周六2、重心问题、重心问题202024/11/2 周六例例3 例例2中中，七七个个居居民民区区的的学学生生人人数数分分别别为为：40、25、45、30、20、35、50人人，学学校校应应建建在在哪哪个个居居民民区区，才才能能使使大大家家都都方方便便？（图中距离单位：百米）。（图中距离单位：百米）。212024/11/2 周六222024/11/2 周六简易公路建设方案简易公路建设方案简易公路建设方案简易公路建设方案某合同某合同战术训练基地基地为保障即将保障即将进行的行的联合合军事演事演习，准，准备在原有的在原有的1个油个油库的基的基础上，再上，再设立立7个固个固定的燃料定的燃料补给点。点。23v1v7v6v2v8v5v3v4油油库与与补给点的位置如点的位置如图所示，其中油所示，其中油库位于位于v1点，点，补给点位于点位于v2,v8点。点。242024/11/2 周六经过前期的前期的测绘工作，如果在油工作，如果在油库和和补给点之点之间修建修建简易公路，由于地形不同，每段公路花易公路，由于地形不同，每段公路花费如如图，每，每单位位费用用为1万元。万元。请根据根据测绘结果，果，规划一个划一个总造价造价最低的建最低的建设方案。方案。v1v7v6v2v8v5v3v425734326436174182总造价最低造价最低各各补给点到油点到油库的的花花费均达到最小均达到最小？252024/11/2 周六