第8讲最短路问题实验.ppt

上传人:王** 文档编号:623698 上传时间:2023-12-08 格式:PPT 页数:28 大小:750.50KB
下载 相关 举报
第8讲最短路问题实验.ppt_第1页
第1页 / 共28页
第8讲最短路问题实验.ppt_第2页
第2页 / 共28页
第8讲最短路问题实验.ppt_第3页
第3页 / 共28页
第8讲最短路问题实验.ppt_第4页
第4页 / 共28页
第8讲最短路问题实验.ppt_第5页
第5页 / 共28页
第8讲最短路问题实验.ppt_第6页
第6页 / 共28页
第8讲最短路问题实验.ppt_第7页
第7页 / 共28页
第8讲最短路问题实验.ppt_第8页
第8页 / 共28页
第8讲最短路问题实验.ppt_第9页
第9页 / 共28页
第8讲最短路问题实验.ppt_第10页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《第8讲最短路问题实验.ppt》由会员分享,可在线阅读,更多相关《第8讲最短路问题实验.ppt(28页珍藏版)》请在优知文库上搜索。

1、数学模型与数学实验数学模型与数学实验 图论模型图论模型实验目的实验目的实验内容实验内容2、会用、会用Matlab软件求最短路软件求最短路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图、图 论论 的的 基基 本本 概概 念念2、最、最 短短 路路 问问 题题 及及 其其 算算 法法3、最、最 短短 路路 的的 应应 用用4、实验作业、实验作业固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径,且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条,则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路算法步骤:

2、算法步骤:)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul1u2u3u 4u5u6u 7u 8u最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8 w=;function l,z=Dijkstra(W)n=size(W,1);for i=1:n l(i)=W(1,i);z(i)=1;en

3、d i=1;while il(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j;if jD(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);end end end end p=sp;mp=sp;for k=1:n if mp=ep d=path(mp,ep);p=p,d;mp=d;end end d=D(sp,ep);path=p一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选选 址址 问问 题题1、中心问题中心问题2、重心问题重心问题购购置置年年份份12345单位(万元)11111212

4、13使用年数 0-1 1-2 2-3 3-4 4-5维维修修费费用用(万万元元)5681118v1v2v3v4v5v6(2)计算在各点iv设立服务设施的最大服务距离)(ivS max)(1ijjidvS ,2,1i 选址问题选址问题-中心问题中心问题例例 2某城市要建立一个消防站,为该市所属的七个区服务,如图所示问应设在那个区,才能使它至最远区的路径最短(1)用 Floyd 算法求出距离矩阵 D=)(ijd(3)求出顶点kv,使)(min)(1iikvSvS则kv就是要求的建立消防站的地点此点称为图的中心点中心点05.15.55.86475.10475.45.25.55.54032475.87

5、30571065.42502545.24720375.5710530DS(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处。选址问题选址问题-重心问题重心问题例例 3某矿区有七个矿点,如图所示已知各矿点每天的产矿量)(jvq(标在图的各顶点上)现要从这七个矿点选一个来建造矿厂 问应选在哪个矿点,才能使各矿点所产的矿运到选矿厂所在地的总运力(千吨公里)最小(1)求距离阵 D=)(ijd(2)计算各顶点作为选矿厂的总运力)(ivm ijjjidvqvm)()(1 ,2,1i(3)求kv使)(m

6、in)(1iikvmvm,则kv就是选矿厂应设之矿点此点称为图 G 的重心重心或中位点中位点实验作业实验作业 可在下面两个题中任选其一可在下面两个题中任选其一1.下表为某工程的全部工序以及工序时间与 紧前工序,工 序ABCDEFGHIJK工序时间(天)247310243232紧前工序/AAABC,D,KE,FDHG,IB请完成以下问题:1).给出工程网络图;2).计算完成整个工程至少需要多少天(总工期)。3).请问不误总工期的前提下,工程H可否延误?最多能够延误多少天?2、选址问题、选址问题 现准备在7个居民点中设置一银行,路线与距离如下图,问设在哪个点,可使 最大服务距离最小?若设两个银行点呢?

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

当前位置:首页 > 高等教育 > 大学课件

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!