第8讲 最短路问题实验

数学模型与数学实验

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

n=size(W,1);

fori=1:n

l(i)=W(1,i);

z(i)=1;

end

i=1;

whilei<=n

forj=1:n

6ifl(i)>l(j)+W(j,i)

l(i)=l(j)+W(j,i);

z(i)=j;

ifj<i

i=j-1;

end

end

end

i=i+1;

end

7floyd算法的基本思想8算法原理——求距离矩阵的方法9算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．10ij算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：11算法步骤12a=[];n=size(a,1);D=a;path=zeros(n,n);fori=1:n

forj=1:n

ifD(i,j)~=inf

path(i,j)=j;%j是i的后续点

end

endendfork=1:n

fori=1:n

forj=1:n

ifD(i,j)>D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j);

13path(i,j)=path(i,k);

end

end

endendp=[sp];mp=sp;fork=1:n

ifmp~=ep

d=path(mp,ep);

p=[p,d];

mp=d;

endendd=D(sp,ep);path=p14一、可化为最短路问题的多阶段决策问题二、选址问题1、中心问题2、重心问题15例：企业要制定一台重要设备更新的五年计划，目标是使总费用（购置费用和维修费用之和）为最小。此设备在各年初价格及使用期中所需维修数据如下：16解：用点vi表示年初。（i=1,2,…6），v6表示第五年底。弧aij=（vi，vj）表示第i年初购置设备使用到第j年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从v1到v6的一条最短路。17v1v2v3v4v5v616221817171630415931234130222318

选址问题--中心问题19S(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处。20

选址问题--重心问题21实验作业

可在下面两个题中任选其一1.下表为某工程的全部工序以及工序时间与紧前工序，工序ABCDEFGHIJK工序时间（天）247310243232紧前工序/AAABC,D,KE,FDHG,IB请完成以下问题：1）.给出工程网络图；2）.计算完成整个工程至少需要多少天（总工期）。3）.请问不误总工期的前提下，工程H可否延误？最多能够延误多少天？222、选址问题