数学建模～最短路问题(课件ppt)

最短路问题二、最小生成树问题及其解法三、最短路问题及其解法一、图论的基本概念图论的基本概念一、图的概念1．图的定义2．顶点的次数3．子图二、图的矩阵表示1．关联矩阵2．邻接矩阵返回定义有序三元组G=(V,E,)称为一个图,如果：[1]V=},,,{21nvvv是有限非空集，V称为顶点集，其中的元素叫图G的顶点.[2]E称为边集，其中的元素叫图G的边.[3]是从边集E到顶点集V中的有序或无序的元素偶对构成集合的映射，称为关联函数.例1设G=(V,E,)，其中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5},112213314414544(),(),(),(),()evvevvevvevvevv.G的图解如图图的定义定义在图G中，与V中的有序偶(vi，vj)对应的边e，称为图的有向边（或弧），而与V中顶点的无序偶vivj相对应的边e，称为图的无向边.每一条边都是无向边的图，叫无向图；每一条边都是有向边的图，称为有向图；既有无向边又有有向边的图称为混合图.定义若将图G的每一条边e都对应一个实数w(e)，则称w(e)为边的权，并称图G为赋权图.规定用记号和分别表示图的顶点数和边数.常用术语：（１）端点相同的边称为环．（２）若一对顶点之间有两条以上的边联结，则这些边称为重边．（３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边．（４）边和它的端点称为互相关联的．（５）既没有环也没有平行边的图，称为简单图．（６）任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n为顶点的数目．(7)若V=XY，XY=，且X中任两顶点不相邻，Y中任两顶点不相邻，则称G为二元图；若X中每一顶点皆与Y中一切顶点相邻，则G称为完备二元图，记为Km,n，其中m,n分别为X与Y的顶点数目．返回顶点的次数定义（１）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为()dv．（２）在有向图中，从顶点v引出的边的数目称为v的出度，记为()dv＋，从顶点v引入的边的数目称为v的入度，记为()dv－，()dv=()dv＋+()dv－称为v的次数．4()4dv5)(3)(2)(444vdvdvd定理１)(2)()(GvdGVv推论１任何图中奇次顶点的总数必为偶数．例2在一次聚会中，史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，房间里的一些人都要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。那么史密斯太太和别人握了几次手呢？返回例1在一次聚会中，认识奇数个人的人数一定是偶数。由图可知，8号的配偶是0号。7号的配偶是1号。6号的配偶是2号。5号的配偶是3号。史密斯太太是4号，所以史密斯太太和别人握了4次手。返回邻接矩阵对无向图Ｇ，其邻接矩阵)(ijaA，其中：不相邻与若相邻与若jijiijvvvva01注：假设图为简单图A=432143210111101011011010vvvvvvvv对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵)(ijaA，其中：EvvEvvajijiij），若（），若（01对有向赋权图Ｇ，其邻接矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义．A=4321432105375083802720vvvvvvvv返回最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路返回基本概念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv定义１在无向图G=(V,E,)中：（１）顶点与边相互交错且iiivve1)((i=1,2,…,k)的有限非空序列)(12110kkkvevevevw称为一条从0v到kv的通路，记为kvvW0（２）边不重复但顶点可重复的通路称为道路，记为kvvT0（３）边与顶点均不重复的通路称为路径，记为kvvP0定义２（１）任意两点均有路径的图称为连通图．（２）起点与终点重合的路径称为圈．（３）连通而无圈的图称为树．定义３（１）设(,)Puv是赋权图G中从u到v的路径，则称)()()(PEeewPw为路径P的权．(2)在赋权图G中，从顶点u到顶点v的具有最小权的路(,)Puv，称为u到v的最短路．返回返回求图的最小生成树最常用的两种算法：（1）Prim算法（2）Kruskal算法注意：在一个加权连通图G中，权最小的那棵生成树称为图G的最小生成树。返回Prim算法思想：输入加权图的带权邻接矩阵（1）建立初始候选边集B，；（2）从候选边中选取最短边（u,v），；（3）调整候选边集B；（4）重复（2）、（3）直到T含有n-1条边。nnjia),(T),(vuTTPrim算法的实现过程123548157610934523111123458inf15439453527236实现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);endwhilesize(T,2)n-1[min,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;endendendKruskal算法思想：假设给定了一个加权连通图G，G的边集合为E，顶点个数n，则假设最小生成树T中的边和顶点均涂为红色，其余为白色。初始时G中的边均为白色。（1）将所有的顶点涂成红色；（2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红。（3）重复（2）直到n-1条红色边，这n-1条红色边就构成了最小生成树T的边集合。注意：在用Kruskal算法求最小生成树时，在第（2）步判断是否形成圈在程序实现时比较麻烦。实现Kruskal算法的MATLAB程序：%加权图的存储结构采用边权矩阵[b(i,j)]m×3b=[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,cKruskal实现过程：初始化后排序：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为根的树．因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．Dijkstra算法：求G中从顶点0u到其余顶点的最短路.设G为赋权有向图或无向图，G边上的权均非负．对每个顶点，定义两个标记（lv()，zv()），其中:lv()：表从顶点0u到v的一条路的权．zv()：v的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终lv()为从顶点0u到v的最短路的权．S：具有永久标号的顶点集输入:G的带权邻接矩阵),(vuw算法步骤：（１）赋初值：令S＝{u0},lu()0=0SVSv\,令lv()=Wuv(,)0,zv()=u0uu0（3）设v*是使lv()取最小值的S中的顶点，则令S=S∪{v*}，uv*（4）若Sφ，转2，否则，停止.用上述算法求出的lv()就是u0到v的最短路的权，从v的父亲标记)(vz追溯到u0,就得到u0到v的最短路的路线.（2）更新lv()、zv()：vSVS\,若lv()luWuv()(,)则令lv()=luWuv()(,),zv()=u例求下图从顶点u1到其余顶点的最短路．先写出带权邻接矩阵：03064093021509701608120W因G是无向图，故W是对称矩阵．TOMATLAB(road1))(iul迭代次数1u2u3u4u5u6u7u8u１2345678０0２１８281083108610127101291212最后标记:)(vl)(vz0217369121u1u1u6u2u5u4u5u)(iul1u2u3u4u5u6u7u8u最后标记:)(vl)(vz0217369121u1u1u6u2u5u4u5u12345678返回uuuuuuuuDijkstra算法的MATLAB实现：w=[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;...8670512inf;inf1inf503inf9;infinfinf13046;...infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);%赋初值fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1；whilekn%更新l(v)和z(v)fori=1:nforj=1:kifi~=s(j)ifl(i)l(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;endendendlv=inf;fori=1:nifll(i)lvlv=ll(i);v=i;endendlv,vs(k+1)=vk=k+1u=s(k)endl,z每对顶点之间的最短路1．求距离矩阵的方法2．求路径矩阵的方法3．查找最短路路径的方法（一）算法的基本思想（三）算法步骤返回（二）算法原理算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵D(1)、D(2)、…、D()，使最后得到的矩阵D()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径．返回算法原理——求距离矩阵的方法把带权邻接矩阵W作为距离矩阵的初值，即D(0)=)()0(ijd=W（１）D(1)=)()1(ijd，其中)0(1)0()1(,min{iijijdd