《短路问题实验.ppt》由会员分享，可在线阅读，更多相关《短路问题实验.ppt（28页珍藏版）》请在三一文库上搜索。
1、数学模型与数学实验,图论模型,实验目的,实验内容,2、会用Matlab软件求最短路,1、了解最短路的算法及其应用,1、图 论 的 基 本 概 念,2、最 短 路 问 题 及 其 算 法,3、最 短 路 的 应 用,4、实验作业,固 定 起 点 的 最 短 路,最短路是一条路径，且最短路的任一段也是最短路,假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路,算法步骤：,u1,u2,u3,u4,u5,u6,u7,u8,w= ; function l,z=Dijkstra(W)n = size (W,1);
2、for i = 1 :n l(i)=W(1,i); z(i)=1;end i=1;while i=n for j =1 :n,if l(i)l(j)+W(j,i) l(i)=l(j)+W(j,i); z(i)=j; if ji i=j-1; end end end i=i+1;end,floyd算法的基本思想,算法原理 求距离矩阵的方法,算法原理 求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R,即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径,算法原理 查找最短路路径的方法,pk,p2,p1,p3,q1,q2,qm,则由点
3、i到j的最短路的路径为：,算法步骤,a= ; n=size(a,1); D=a; path=zeros(n,n); for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; %j是i的后续点 end end end for k=1:n for i=1:n for j=1:n if D(i,j)D(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; en
4、d end d=D(sp,ep); path=p,一、 可化为最短路问题的多阶段决策问题,二、 选 址 问 题,1、 中心问题,2、 重心问题,例：企业要制定一台重要设备更新的五年计划，目标是使总费用（购置费用和维修费用之和）为最小。此设备在各年初价格及使用期中所需维修数据如下：,解：用点vi表示年初。（i=1,2,6）， v6表示第五年底。弧aij=（vi，vj）表示第i年初购置设备使用到第j年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从v1到v6的一条最短路。,v1,v2,v3,v4,v5,v6,16,22,18,17,17,16,30,41,59,31,23,41,
5、30,22,23,选址问题-中心问题,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处。,选址问题-重心问题,实验作业,可在下面两个题中任选其一,1. 下表为某工程的全部工序以及工序时间与 紧前工序，,请完成以下问题： 1）. 给出工程网络图； 2）. 计算完成整个工程至少需要多少天（总工期）。 3）. 请问不误总工期的前提下，工程H可否延误？ 最多能够延误多少天？,2、选址问题 现准备在7个居民点中设置一银行， 路线与距离如下图，问设在哪个点，可使 最大服务距离最小？若设两个银行点呢？,