数学建模～最短路问题

最短路问题,二、最小生成树问题及其解法,三、最短路问题及其解法,一、图论的基本概念,图论的基本概念,一、图的概念,1图的定义,2顶点的次数,3子图,二、图的矩阵表示,1关联矩阵,2邻接矩阵,返回,图的定义,定义,定义,返回,顶点的次数,例2在一次聚会中，史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，房间里的一些人都要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。那么史密斯太太和别人握了几次手呢？,返回,例1在一次聚会中，认识奇数个人的人数一定是偶数。,由图可知，8号的配偶是0号。7号的配偶是1号。6号的配偶是2号。5号的配偶是3号。史密斯太太是4号，所以史密斯太太和别人握了4次手。,返回,邻接矩阵,注：假设图为简单图,返回,最短路问题及其算法,一、基本概念,二、固定起点的最短路,三、每对顶点之间的最短路,返回,基本概念,返回,返回,求图的最小生成树最常用的两种算法：（1）Prim算法（2）Kruskal算法,注意：在一个加权连通图G中，权最小的那棵生成树称为图G的最小生成树。,返回,Prim算法思想：输入加权图的带权邻接矩阵（1）建立初始候选边集B，；（2）从候选边中选取最短边（u,v），；（3）调整候选边集B；（4）重复（2）、（3）直到T含有n-1条边。,Prim算法的实现过程,111123458inf15,439,453,527,236,实现Prim算法的MATLAB程序：a=08inf15;806inf7;inf60910;1inf903;571030;T=;e=0;v=1;n=5;sb=2:n;%1代表第一个红点，sb代表白点集。forj=2:n%构造初始候选边的集合b(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);end,whilesize(T,2)n-1min,i=min(b(3,:);%在候选边中找最短边。T(:,size(T,2)+1)=b(:,i);e=e+b(3,i);v=b(2,i);v表示新涂的红点。temp=find(sb=b(2,i);sb(temp)=;b(:,i)=;forj=1:length(sb)%调整候选边d=a(v,b(2,j);ifdb(3,j)b(1,j)=v;b(3,j)=d;endendend,Kruskal算法思想：假设给定了一个加权连通图G，G的边集合为E，顶点个数n，则假设最小生成树T中的边和顶点均涂为红色，其余为白色。初始时G中的边均为白色。（1）将所有的顶点涂成红色；（2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红。（3）重复（2）直到n-1条红色边，这n-1条红色边就构成了最小生成树T的边集合。注意：在用Kruskal算法求最小生成树时，在第（2）步判断是否形成圈在程序实现时比较麻烦。,实现Kruskal算法的MATLAB程序：%加权图的存储结构采用边权矩阵b(i,j)m3b=1112233424535455815679103;B,I=sortrows(b,3);B=B;m=size(b,2);n=5;t=1:n;k=0;T=;c=0;,fori=1:mift(B(1,i)=t(B(2,i)%判断第i条边是否与树中的边形成圈。k=k+1;T(k,1:2)=B(1:2,i);c=c+B(3,i);tmin=min(t(B(1,i),t(B(2,i);tmax=max(t(B(1,i),t(B(2,i);forj=1:nift(j)=tmaxt(j)=tmin;endendendifk=n-1break;endendT,c,Kruskal实现过程：初始化后排序：B=1412213345535245135678910；第一轮：tmin=1;tmax=4;t=12315;第二轮：tmin=4;tmax=5;t=12311;第三轮：t(1)=t(5)直接进入下一轮第四轮：tmin=2;tmax=3;t=12211;第五轮：tmin=1;tmax=2;t=11111;,求最短路径的最常用的两种算法：（1）Dijkstra算法（2）Floyd算法,注意：普通路径长度定义为该路径所包含的全体边的长度之和。最短路径是指在图中，从顶点u到顶点v的路径中普通路径长度最短的路径称为u到v的最短路径。,固定起点的最短路,最短路是一条路径，且最短路的任一段也是最短路,假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此,可采用树生长的过程来求指定顶点到其余顶点的最短路,算法步骤：,TOMATLAB(road1),1,2,3,4,5,6,7,8,返回,Dijkstra算法的MATLAB实现：w=0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;.8670512inf;inf1inf503inf9;infinfinf13046;.infinf92inf403;infinfinfinf9630n=size(w,1);w1=w(1,:);%赋初值fori=1:nl(i)=w1(i);z(i)=1;ends=;s(1)=1;u=s(1);k=1；,whilekl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendl,z,%求v*ll=l;fori=1:nforj=1:kifi=s(j)ll(i)=ll(i);elsell(i)=inf;endendend,lv=inf;fori=1:nifll(i)lvlv=ll(i);v=i;endendlv,vs(k+1)=vk=k+1u=s(k)endl,z,每对顶点之间的最短路,1求距离矩阵的方法,2求路径矩阵的方法,3查找最短路路径的方法,（一）算法的基本思想,（三）算法步骤,返回,（二）算法原理,算法的基本思想,返回,算法原理求距离矩阵的方法,返回,算法原理求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R,即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径,返回,算法原理查找最短路路径的方法,pk,p2,p1,p3,q1,q2,qm,则由点i到j的最短路的路径为：,返回,算法步骤,TOMATLAB(road2(floyd),返回,Folyd算法的MATLAB实现：functionD,R=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endend,fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendk,D,Rend,在命令窗口中输入：a=09inf3inf;902inf7;inf2024;3inf20inf;inf74inf0;floyd(a),一、可化为最短路问题的多阶段决策问题,二、选址问题,1中心问题,2重心问题,返回,可化为最短路问题的多阶段决策问题,返回,选址问题-中心问题,TOMATLAB(road3(floyd),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处.,返回,选址问题-重心问题,返回,实验作业,生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率.生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会.可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益.,某生产厂家年初要