最短路的Floyd算法.ppt

上传人:小飞机 文档编号:5753204 上传时间:2023-08-16 格式:PPT 页数:16 大小:209KB
返回 下载 相关 举报
最短路的Floyd算法.ppt_第1页
第1页 / 共16页
最短路的Floyd算法.ppt_第2页
第2页 / 共16页
最短路的Floyd算法.ppt_第3页
第3页 / 共16页
最短路的Floyd算法.ppt_第4页
第4页 / 共16页
最短路的Floyd算法.ppt_第5页
第5页 / 共16页
点击查看更多>>
资源描述

《最短路的Floyd算法.ppt》由会员分享,可在线阅读,更多相关《最短路的Floyd算法.ppt(16页珍藏版)》请在三一办公上搜索。

1、运筹学,讲课教师:熊德国,河南理工大学能源科学与工程学院,最短路的Floyd算法,FLOYD 算法 以上介绍的算法用来求源点至各点的最短路。在有些问题中,我们需要知道节点两两之间的最短路,比如选址问题。这类问题可以用DIJKSTRA算法,依次改变源点来求解,但计算比较繁琐。现在介绍一种直接计算任意两节点之间最短路的方法Floyd算法,该算法由Floyd于1962年提出。,最短路的Floyd算法,Floyd算法是权矩阵迭代算法,记网络的权矩阵为,其中,最短路的Floyd算法,算法基本步骤为:,(2)计算,其中,,(3)重复(2),直到,此时,即为节点i到点j的最短路的距离。,(1)令,最短路的F

2、loyd算法,例4.3.4 用Floyd算法计算图421中任意两节点间的最短路。,最短路的Floyd算法,解:写出图421的权矩阵D,并令,最短路的Floyd算法,最短路的Floyd算法,D1的元素d1ij的意义为i直接到达j及经节点1到达j的两种方式中,最短路线的距离;,最短路的Floyd算法,最短路的Floyd算法,D2的元素d2ij的意义为i直接到达j及最多经节点1、2到达j的所有方式中,最短路线的距离,这些可能的方式有:i-j,i-1-j,i-2-j,i-1-2-j,i-2-1-j。例如d2434423表示节点4到节点3在这些方式中取423为最短路,距离为4。下标423便于在算法结束时

3、确定最短路之用。,最短路的Floyd算法,最短路的Floyd算法,最短路的Floyd算法,任意两节点之间的最短路,最多可经过节点1、2n到达,因此当计算到Dn时,算法已结束,至此,得到任意两点间的最短路及其距离。如本例题中,节点1、6之间的最短路为1246,距离为9;节点3、4之间的最短路为354,距离为3;节点6、4之间的最短路为64,距离为3,等等。,最短路的Floyd算法,例4.3.5 选址问题最短路问题的应用II 图422为某地区的居民区分布图,各边旁的数据为居民区间的距离,拟在其中一个居民区建一个大型超市,问超市建在那里,才能使距离超市最远的居民到超市的距离最近?,最短路的Floyd算法,解:如果超市建在i点,则需计算出i至各点的最短路的距离,其中最大者即离超市最远,于是问题变成求这些最大最短路中的最小者。,最短路的Floyd算法,为此需计算任意两点间的最短路。,表示节点i到各节点的最短路中的最大值。,超市应建在第6居民区,到超市最远的居民区为节点5所示的小区,距离为48。,用Floyd算法计算结果为下列矩阵D。,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号