• / 16
  • 下载费用:10 金币  

实验8(floyd算法).ppt

关 键 词:
实验8(floyd算法).ppt
资源描述:
lzb8401552@hgnu.edu.cn,最 短 路 算 法,任意一对顶点之间的最短路算法:Floyd算法,lzb8401552@hgnu.edu.cn,,1、求距离矩阵的方法,2、求路径矩阵的方法,3、查找最短路路径的方法,(一)算法的基本思想,(三)算法步骤,lzb8401552@hgnu.edu.cn,算法的基本思想,lzb8401552@hgnu.edu.cn,算法原理—— 求距离矩阵的方法,lzb8401552@hgnu.edu.cn,算法原理—— 求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R.,即当vk被插入任何两点间的最短路径时,被记录在R(k)中,依次求 时求得 ,可由 来查找任何点对之间最短路的路径.,lzb8401552@hgnu.edu.cn,算法原理—— 查找最短路路径的方法,,,,,,,,pk,p2,p1,p3,q1,q2,qm,则由点i到j的最短路的路径为:,lzb8401552@hgnu.edu.cn,算法步骤,自定义floyd函数,function [d,r]=floyd(w) n=length(w); for i=1:nfor j=1:nd(i,j)=w(i,j);r(i,j)=j;end end for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=k;endendend end,,,,,,clear; w=[0,9,inf,3,inf;9,0,2,inf,7;inf,2,0,2,4;3,inf,2,0,inf;inf,7,4,inf,0]; [d,r]=floyd(w),选址问题--中心问题,clear; w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0]; [d,r]=floyd(w) S=max(d’) %求矩阵各列的最大值 s=min(S),lzb8401552@hgnu.edu.cn,S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5,S(v3)=6,故应将消防站设在v3处。,lzb8401552@hgnu.edu.cn,选址问题--重心问题,lzb8401552@hgnu.edu.cn,clear; w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,inf,4,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,1,inf,inf;inf,inf,2,1,0,4,inf;inf,4,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0]; [d,r]=floyd(w) q=[3,2,7,1,6,1,4]; for i=1:7m1=0;for j=1:7m1=m1+q(j)*d(i,j);endm(i)=m1; end m min(m),lzb8401552@hgnu.edu.cn,d = 0 3.0000 5.0000 8.0000 7.0000 7.0000 8.50003.0000 0 2.0000 5.0000 4.0000 4.0000 5.50005.0000 2.0000 0 3.0000 2.0000 6.0000 7.50008.0000 5.0000 3.0000 0 1.0000 5.0000 6.50007.0000 4.0000 2.0000 1.0000 0 4.0000 5.50007.0000 4.0000 6.0000 5.0000 4.0000 0 1.50008.5000 5.5000 7.5000 6.5000 5.5000 1.5000 0m =132 78 70 92 70 106 130 ans =70,lzb8401552@hgnu.edu.cn,实验八、最佳灾情巡视路线(节选部分),实验内容:求出下图中O到其它各点的最短路线(要求求出最短路线及其最短距离)(节选了教材上337面图中的16个点:即15、16、17、18、20、21、22、23、25、26、I、K、M、N、O、P等16个点),lzb8401552@hgnu.edu.cn,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:实验8(floyd算法).ppt
链接地址:https://www.weizhuannet.com/p-9847355.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开