最短路问题实验.pptx

实验目的实验目的实验内容实验内容2、会用、会用Matlab软件求最短路软件求最短路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图、图 论论 的的 基基 本本 概概 念念2、最、最 短短 路路 问问 题题 及及 其其 算算 法法3、最、最 短短 路路 的的 应应 用用4、实验作业、实验作业固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树因此,可采用树生长的过程来求指定顶点到其余顶点的最短路算法步骤：算法步骤：u1u2u3u4u5u6u7u8w=;functionl,z=Dijkstra(W)n=size(W,1);fori=1:nl(i)=W(1,i);z(i)=1;endi=1;whileil(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j;ifjD(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendp=sp;mp=sp;fork=1:nifmp=epd=path(mp,ep);p=p,d;mp=d;endendd=D(sp,ep);path=p一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选选 址址 问问 题题1、中心问题中心问题2、重心问题重心问题例：例：企业要制定一台重要设备企业要制定一台重要设备更新的五年计划，目标是使总更新的五年计划，目标是使总费用（购置费用和维修费用之费用（购置费用和维修费用之和）为最小。此设备在各年初和）为最小。此设备在各年初价格及使用期中所需维修数据价格及使用期中所需维修数据如下：如下：解：解：用点用点vi vi表示年初。表示年初。（i=1,2,i=1,2,6 6），），v v6 6表示第五年底。表示第五年底。弧弧a aij ij=（v vi i，v vj j）表示第）表示第i i年初购置年初购置设备使用到第设备使用到第j j年初的过程。对应年初的过程。对应的权期间发生的购置费用和维修的权期间发生的购置费用和维修费用之和。原问题转变为从费用之和。原问题转变为从v v1 1到到v v6 6的一条最短路。的一条最短路。v1v2v3v4v5v6161622221818171717171616303041415959313123234141303022222323选址问题选址问题-中心问题中心问题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处。选址问题选址问题-重心问题重心问题实验作业实验作业可在下面两个题中任选其一可在下面两个题中任选其一1.下表为某工程的全部工序以及工序时间与紧前工序，工序ABCDEFGHIJK工序时间（天）247310243232紧前工序/AAABC,D,KE,FDHG,IB请完成以下问题：1）.给出工程网络图；2）.计算完成整个工程至少需要多少天（总工期）。3）.请问不误总工期的前提下，工程H可否延误？最多能够延误多少天？2、选址问题、选址问题现准备在7个居民点中设置一银行，路线与距离如下图，问设在哪个点，可使最大服务距离最小？若设两个银行点呢？