Matlab编程第七章-图与网络分析模型选讲课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 图与网络分析模型选讲,一、图论的基本知识,1.,图的概念,定义 图,G,(,V,E,),是指一个二元组,(,V,(,G,),E,(,G,),，其中,:,(1),V,(,G,)=,v,1,v,2,v,n,是非空有限集，称为顶点集，,(2),E,(,G,),是,V,(,G,),中的元素对,(,v,i,v,j,),组成的集合,称为边集,。,图,G,：,V,(,G,)=,v,1,v,2,v,3,v,4,E,(,G,)= ,e,1,e,2,e,3,e,4,e,5,e,6,e,3,=(,v,1,v,3,),第七章 图与网络分析模型选讲一、图论的基本知识1.图的概念,若图,G,是的边是有方向的，称,G,是有向图，有向图的边称为有向边或弧。,常用术语,边和它的两端点称为互相关联,.,与同一条边关联的两个端点称,为相邻的顶点，与同一个顶点,点关联的两条边称为相邻的边,.,3),端点重合为一点的边称为环,.,4),若一对顶点之间有两条以上的边联结，则这些边称为重边,5),既没有环也没有重边的图，称为简单图,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,若图G是的边是有方向的，称G是有向图，有向图的边称为有向边或,6),若图,G,的每一条边,e,都赋以一个实数,w,(,e,),，,称,w,(,e,),为边,e,的权，,G,连同边上的权称为赋权图,记为：,G,(,V,E,W,),，,W,=,w,(,e,)|,e,E,v,1,v,2,v,3,v,4,5,3,2,7),图,G,的中顶点的个数，,称为图,G,的阶；图中与某个顶点相关联的边的数目，称为该顶点的度。,8,）完全图：若无向图的任意两个顶点之间都存在着一条边，称此图为完全图。,6) 若图G的每一条边e 都赋以一个实数w(e)，v1v2v,2.,图的矩阵表示,邻接矩阵,: (,以下均假设图为简单图,).,图,G,的邻接矩阵是表示顶点之间相邻关系的矩阵：,A,=(,a,ij,),，,若,v,i,与,v,j,相邻,若,v,i,与,v,j,不相邻,或权值，,或,，,其中：,2.图的矩阵表示若vi与vj相邻若vi与vj不相邻或权值，或,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,5,4,3,1,无向图,G,邻接矩阵,A,=(,a,ij,),v1v2v3v4v1v2v3v45431无向图G邻接矩阵A=,有向图,G,邻接矩阵,A,=(,a,ij,),v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,5,4,3,1,有向图G邻接矩阵A=(aij)v1v2v3v4v1v2v3v,二、最大流问题,定义：设,G,(,V,E,),为有向图，若在每条边,e,上定义一个非负权,c,，则称图,G,为一个网络，称,c,为边,e,的容量函数，,记为,c,(,e,),。,若在有向图,G,(,V,E,),中有两个不同的顶点,v,s,与,v,t,，,若顶点,v,s,只有出度没有入度，称,v,s,为图,G,的源，,若顶点,v,t,只有入度没有出度，称为,G,的汇，,若顶点,v,既不是源也不是汇，称为,v,中间顶点。,v,2,v,4,v,1,v,3,v,s,v,t,4,8,3,7,5,7,3,7,二、最大流问题定义：设G(V,E)为有向图，若在每条边e上定,v,2,v,4,v,1,v,3,v,s,v,t,4,8,3,7,5,7,3,7,设,u,v,网络,G,(,V,E,),的相邻顶点，边,(,u,v,),上的函数,f,(,u,v,),称为边,(,u,v,),上的实际流量；,若对网络,G,(,V,E,),的任意相邻顶点,u,v,均成立：,0,f,(,u,v,) ,c,(,u,v,),，,称该网络为相容网络。,若,v,为网络,G,(,V,E,),的中间顶点，,有：,v2v4v1v3vsvt48375737设u,v网络G(V,v,2,v,4,v,1,v,3,v,s,v,t,4,8,3,7,5,7,3,7,网络的总流量为从源,v,s,流出的总流量：,流入汇,v,t,总流量：,v2v4v1v3vsvt48375737网络的总流量为从源v,定义：设网络,G,(,V,E,),为相容网络，,u,v,是,G,的相邻顶点，,G,的容量函数为,c,(,u,v,),，实际流量函数为,f,(,u,v,),，,v,s,和,v,t,分别为,G,(,V,E,),的源和汇，,V,(,f,),为从源,v,s,流出的总流量，,若：,则称该网络称为守恒网络。,守恒网络中的流,f,称为可行流。,若存在一个可行流,f,*,，使得对所有可行流,f,都有,V,(,f,*),V,(,f,),成立，则称,f,*,为最大流。,定义：设网络G(V,E)为相容网络，u,v是G的相邻顶点，,最大流模型：,s.t:,最大流模型：s.t:,例,7.1,分组交换技术在计算机网络中发挥着重要作用，信息从源节点到目的节点不再需要一条固定的路径，而是将其分割为几组，通过不同的路径传输到目的节点，目的节点再重新组合还原文件。现考察如图所示的网络，图中两节点间的数字表示两交换机间可用的带宽，此时从节点,1,到节点,9,的最大带宽为多少？,v,2,v,5,v,1,v,3,v,8,2.5,v,9,v,4,v,7,v,6,7.1,3.4,6.1,5.6,2.4,3.6,3.8,7.4,4.9,5.7,7.2,5.3,4.5,3.8,6.7,7.4,例7.1分组交换技术在计算机网络中发挥着重要作用，信息从源节,设,f,ij,为从,v,i,到,v,j,的实际流量，得一个,9,阶方阵：,F,=(,f,ij,),记容量矩阵为,C,=,0 2.5 0 5.6 6.1 0 0 0 0,0 0 7.1 0 0 3.6 0 0 0,0 0 0 0 0 0 0 3.4 0,0 0 0 0 4.9 0 7.4 0 0,0 2.4 0 0 0 7.2 5.7 0 0,0 0 3.8 0 0 0 0 5.3 4.5,0 0 0 0 0 3.8 0 0 6.7,0 0 0 0 0 0 0 0 7.4,0 0 0 0 0 0 0 0 0,v,2,v,5,v,1,v,3,v,8,2.5,v,9,v,4,v,7,v,6,7.1,3.4,6.1,5.6,2.4,3.6,3.8,7.4,4.9,5.7,7.2,5.3,4.5,3.8,6.7,7.4,设fij为从vi到vj的实际流量，得一个9阶方阵：F=( f,Matlab编程第七章-图与网络分析模型选讲课件,sets: node/1.9/;,arc(node,node):c,f;,Endsets,OBJmax=flow;,for(node(i)|i#ne#1#and#i#ne#9:,sum(node(j):f(i,j)=sum(node(j):f(j,i);,sum(node(j): f(1,j)=flow;,sum(node(j): f(j,9)=flow;,for(arc:bnd(0,f,c);,sets: node/1.9/;,data:,c=,0 2.5 0 5.6 6.1 0 0 0 0,0 0 7.1 0 0 3.6 0 0 0,0 0 0 0 0 0 0 3.4 0,0 0 0 0 4.9 0 7.4 0 0,0 2.4 0 0 0 7.2 5.7 0 0,0 0 3.8 0 0 0 0 5.3 4.5,0 0 0 0 0 3.8 0 0 6.7,0 0 0 0 0 0 0 0 7.4,0 0 0 0 0 0 0 0 0;,enddata,data:,该程序运行结果：,最大流：,14.2,F(1,2)=2.5, F(1,4)=5.6,F(1,5)=6.1,F(2,3)=3.4,F(2,6)=1.5,F(3,8)=3.4,F(4,5)=3.3,F(4,7)=2.3,F(5,2)=2.4,F(5,6)=7,F(6,8)=4,F(6,9)=4.5,F(7,9)=2.3,F(8,9)=7.4,v,2,v,5,v,1,v,3,v,8,2.5,v,9,v,4,v,7,v,6,7.1,3.4,6.1,5.6,2.4,3.6,3.8,7.4,4.9,5.7,7.2,5.3,4.5,3.8,6.7,7.4,该程序运行结果：v2v5v1v3v82.5v9v4v7v67,0 2.5 0 5.6 6.1 0 0 0 0,0 0 7.1 0 0 3.6 0 0 0,0 0 0 0 0 0 0 3.4 0,0 0 0 0 4.9 0 7.4 0 0,0 2.4 0 0 0 7.2 5.7 0 0,0 0 3.8 0 0 0 0 5.3 4.5,0 0 0 0 0 3.8 0 0 6.7,0 0 0 0 0 0 0 0 7.4,0 0 0 0 0 0 0 0 0,x=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9;,y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9;,z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;,Matlab,中求最大流的命令：,graphmaxflow(f,a,b),0 2.5 0 5.6 6.1 0,clc,clear,x=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9;,y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9;,z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;,f=sparse(x,y,z),flow,flowmat=graphmaxflow(f,1,9),name1(1:9,1)=v;,name2=int2str(1:9);,name=cellstr(strcat(name1,name2); view(biograph(flowmat,name,ShowWeights,on),clc,clear,三、,旅行售货员问题（,TSP,问题）,一个旅行商，从城市,1,出发，要遍访城市,1,2,3,n,各一次，最后返回城市,1,。若从城市,i,到,j,的旅费为,c,ij,，,问他应按怎样的次序访问这些城市，能使得总旅费最少？,用图论语言描述：在赋权图中，寻找一条经过所有节点，并回到原点的最短路。,包含图,G,的每个顶点的路称为哈密顿路；闭的哈密顿路称为哈密顿圈。,到目前为止，,TSP,问题还没有有效解决方法，现有的方法都是寻找近似最优的哈密顿圈，常用方法有边替换法、遗传算法、模拟退火法、蚁群算法等。,三、旅行售货员问题（TSP问题） 一个旅行商，从城市1出,引入,0-1,变量：,x,ij,=,1,，由第,i,城市进入第,j,城市，且,i,j,0,，其它,目标函数：,对规模不大的,TSP,问题可将其转化为数学规划问题：,j,=1,2,3,n,i,=1,2,3,n,引入0-1变量：xij=1，由第i城市进入第j城市，且i ,1,2,3,4,5,6,到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于,TSP,来说并不充分，,仅仅是必要条件。,例如：,以上两个条件都满足，但它显然不是,TSP,的解，,它存在两个子巡回。,则可以避免产生子巡回。,若在原模型上添加变量,u,i,，,并附加下面形式的约束条件：,123456到此得到了一个模型，它是一个指派问题的整数规划模,目标函数：,s.t,：,i,=2,3,n,i,j,=1,2,3,n,j,=1,2,3,n,i,=1,2,3,n,TSP,问题的数学规划模型：,目标函数： s.t： i=2,3,n i,j=1,2,3,例,7.2 (TSP,问题,),已知,9,个城市间的旅行费用（见表）问他应按怎样的次序访问这些城市，能使得总旅费最少？,0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.3, 5.9,3.1, 0, 4.8, 8.1, 9.3, 8.7, 6.4, 4.5, 7.2,5.2, 4.8, 0, 7.7, 9.5, 4.9, 5.3, 6.6, 6.8,4.3, 8.1, 7.7, 0, 7.3, 11.2, 10.8,9.7, 8.8,5.2, 9.3, 9.5, 7.3, 0, 10.5, 11.3,7.9, 9.4,6.5, 8.8, 4.9, 11.2,10.5, 0, 6.1, 5.8, 7.5,8.8, 6.4, 5.3, 10.8,11.3, 6.1, 0, 6.6, 4.9,7.3, 4.5, 6.6, 9.7, 7.9, 5.8, 6.6, 0, 5.8,5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;,城市编号,1 2 3 4 5 6 7 8 9,1 2 3 4 5 6 7 8 9,例7.2 (TSP问题) 已知9个城市间的旅行费用（见表）问,s.t,：,i,j,=1,2,3,n,sets: city /1.9/:u;,link(city,city):c,x;,endsets,OBJmin=sum(link:c*x);,for(city(j):,sum(city(i)|i#ne#j:x(i,j)=1);,for(city(i):,sum(city(j)|j#ne#i:x(i,j)=1);,for(city(i)|i#gt#1:,for(city(j)|j#gt#1#and#i#ne#j:,u(i)-u(j)+9*x(i,j)=8);,for(city(i)|i#gt#1:u(I)=0);,for(link:bin(x);,s.t： i,j=1,2,3,nsets: city,data:,c=0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.3, 5.9,3.1, 0, 4.8, 8.1, 9.3, 8.7, 6.4, 4.5, 7.2,5.2, 4.8, 0, 7.7, 9.5, 4.9, 5.3, 6.6, 6.8,4.3, 8.1, 7.7, 0, 7.3, 11.2, 10.8,9.7, 8.8,5.2, 9.3, 9.5, 7.3, 0, 10.5, 11.3,7.9, 9.4,6.5, 8.8, 4.9, 11.2,10.5, 0, 6.1, 5.8, 7.5,8.8, 6.4, 5.3, 10.8,11.3, 6.1, 0, 6.6, 4.9,7.3, 4.5, 6.6, 9.7, 7.9, 5.8, 6.6, 0, 5.8,5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;,enddata,data:,Objective value: 49.10000,X( 1, 4) 1.000000,X( 2, 1) 1.000000,X( 3, 2) 1.000000,X( 4, 5) 1.000000,X( 5, 8) 1.000000,X( 6, 3) 1.000000,X( 7, 6) 1.000000,X( 8, 9) 1.000000,X( 9, 7) 1.000000,按如下次序：,1,4,5,8,9,7,6,3,2,1,访问这些城市时总费用最小，最小费用：,49.1,Objective value: 49.10000 按如下,e,i,与,v,i,-1,和,v,i,关联，称 为图,G,的,四、最短路,问题,道路与轨道：在图,G(V,E,),中，设,一条道路，,k,为路长，,v,0,为道路,P,的起点,v,t,为终点，,各边相异的道路称为行迹，,顶点不同且边也不同的道路称为轨道（路径）。,最短路问题：对赋权图,G,(,V,E,W,),，在连接指定起点,v,0,与终点,v,t,的所有轨道,P,中，寻找一条权数之和最小的轨道。,ei与vi-1和vi关联，称,数学模型：,设图,G,(,V,E,W,),顶点,v,0,v,t,V,边,e,E,，,w,(,e,),为边,e,的权数，,P,(,v,0,v,t,),是起点为,v,0,终点为,v,t,为任意一条轨道，,所有这些轨道的全体记为：,S,(,P,),W,(,P,),为轨道,P,(,v,0,v,t,),上各边的权数之和，,最短路问题需要求出：,（,1,）权数之和最小的轨道（,2,）该轨道的权数之和,求解此问题的方法有：,Dijkstra,算法、,floyd,算法，遗传算法、模拟退火、蚁群算法等。,数学模型：最短路问题需要求出：,Dijkstra,算法：（算法具体内容略）,是用来求指定两点,A,与,B,之间的最短路的，,在,matlab,中使用命令,graphshortestpath,实现。,调用格式：,dist,path=graphshortestpath(DG,A,B),dist,：,A,与,B,之间的最短路的长度,path,：,A,与,B,之间的最短路的路径,DG,：权数邻接矩阵,由权数邻接矩阵画图的命令：,view(biograph(DG,ShowWeights,on),Dijkstra算法：（算法具体内容略）,例,7.3,某地,10,个点,v1,v2,v10,间的道路连接情况为：,相邻点,距离,相邻点,距离,相邻点,距离,相邻点,距离,12: 4.2,，,13: 5.6,，,14: 6.5,23: 3.5,，,25: 6.5,，,27: 15.2,34: 3.8,，,35: 5.4,，,36: 7.6,45: 5.1,，,46: 5.1,，,47: 8.8,，,48: 12.3,56: 4.7,，,57: 5.2,，,59: 7.6,67: 6.3,，,68: 3.9,，,69: 5.2,78: 6.9,，,79: 3.5,，,710: 6.3,89: 6.8,，,810: 5.9,，,910: 5.8,求由,v1,到,v10,间的最短路。,例7.3 某地10个点v1,v2,v10间的道路连接情况,clc,clear,x=1:8,1:8,1:7,9,4,10;,y=2:9,3,5,5:10,4,7,6,7,9,9,10,10,8,10;,w=4.2,3.5,3.8,5.1,4.7,6.3,6.9,6.8,5.6,6.5,5.4,5.1,5.2,3.9,3.5,5.9,6.5,15.2,7.6,8.8,7.6,5.2,6.3,5.8,12.3,0;,相邻点,距离,相邻点,距离,相邻点,距离,相邻点,距离,12: 4.2,，,13: 5.6,，,14: 6.5,23: 3.5,，,25: 6.5,，,27: 15.2,34: 3.8,，,35: 5.4,，,36: 7.6,45: 5.1,，,46: 5.1,，,47: 8.8,，,48: 12.3,56: 4.7,，,57: 5.2,，,59: 7.6,67: 6.3,，,68: 3.9,，,69: 5.2,78: 6.9,，,79: 3.5,，,710: 6.3,89: 6.8,，,810: 5.9,，,910: 5.8,clc,clearw=4.2,3.5,3.8,5.1,4.,W=sparse(x,y,w);,B=W+W;,dist,path=graphshortestpath(B,1,10),ids=v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;,h=view(biograph(W,ids,ShowArrows,off,ShowWeights,on,),set(h.Nodes(path),Color,1,0.5,0.5),edges=getedgesbynodeid(h,get(h.Nodes(path),ID);,set(edges,LineColor,0,1,0),set(edges,LineWidth,2),W=sparse(x,y,w);,dist =,21.4000,path =,1 4 6 8 10,dist =,floyd,算法：,设图,G,(,V,E,W,),的权邻接矩阵为：,其中 当,v,i,与,v,j,之间没有边相连时，取,当,v,i,与,v,j,之间有边时，取,w,ij,为该边的权。,对于无向图,G,，邻接矩阵,D,0,是对称矩阵。,floyd算法：,(3),递推产生一个矩阵序列,D,0,D,1,D,n,(4),为最短路距离矩阵，,floyd,算法的步骤：,（求有,n,个节点的图的最短路距离矩阵,D,n,的步骤）,(1),初值,k,=0,，,为,v,i,到,v,j,的最短路的距离。,(2),计算,(3)递推产生一个矩阵序列D0, D1, Dnfloyd,建立最短路径矩阵,R,的步骤：,（,1,）,(3),递推产生一个矩阵序列,R,0,R,1,R,n,(4),矩阵,R=R,n,为最短路径矩阵,建立最短路径矩阵R的步骤：(3)递推产生一个矩阵序列R0,R,查找最短路路径的方法：,若 则 是,点,v,i,与到点,v,j,最短路径的途中点，,(1),向起点,v,i,与追溯：,得：,(2),向终点,v,j,与追溯：,得：,(3),点,v,i,与到点,v,j,最短路路径：,查找最短路路径的方法：若 则,例,7.4,求右图中加权图的任意两点间的最短距离与最短路径,.,1,2,3,5,6,4,6,5,8,5,4,3,6,7,6,6,9,0, 4, 5, 6, 6,4, 0,3,5, 0, 8, 5,8, 0, 6, 9,6, 5, 6, 0, 7,6, 3,9, 7, 0,例7.4 求右图中加权图的任意两点间的最短距离与最短路径.,0, 4, 5, 6, 6,4, 0,3,5, 0, 8, 5,8, 0, 6, 9,6, 5, 6, 0, 7,6, 3,9, 7, 0,(1),k,=1:,0, 4, 5, 6, 6,4, 0, 9,10, 3,5, 9, 0, 8, 5, 11,8, 0, 6, 9,6, 10, 5, 6, 0, 7,6, 3, 11,9, 7, 0,1 2 3 4 5 6,1 2 1 4 1 6,1 1 3 4 5 1,1 2 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,1 2 3 4 5 6,1 2 3 4 5 6,1 2 3 4 5 6,1 2 3 4 5 6,1 2 3 4 5 6,1 2 3 4 5 6,0, 4, 5, , 6, 6(1) k=1: 0,0, 4, 5, 6, 6,4, 0, 9,10, 3,5, 9, 0, 8, 5, 11,8, 0, 6, 9,6, 10, 5, 6, 0, 7,6, 3, 11,9, 7, 0,(2),k,=2:,得,:,1 2 3 4 5 6,1 2 1 4 1 6,1 1 3 4 5 1,1 2 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,0, 4, 5, , 6, 6(2) k=2: 得:,1 2 3 4 5 6,1 2 1 4 1 6,1 1 3 4 5 1,1 2 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,0, 4, 5, 6, 6,4, 0, 9,10, 3,5, 9, 0, 8, 5, 11,8, 0, 6, 9,6, 10, 5, 6, 0, 7,6, 3, 11,9, 7, 0,(3),k,=3:,0 4 5 13 6 6,4 0 9 17 10 3,5 9 0 8 5 11,13 17 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,1 2 3 3 5 6,1 2 1 3 1 6,1 1 3 4 5 1,3 3 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,1 2 3 4 5 60, 4,(4),k,=4:,得,:,1 2 3 3 5 6,1 2 1 3 1 6,1 1 3 4 5 1,3 3 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,0 4 5 13 6 6,4 0 9 17 10 3,5 9 0 8 5 11,13 17 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,(4) k=4: 得: 1 2 3,1 2 3 3 5 6,1 2 1 3 1 6,1 1 3 4 5 1,3 3 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,0 4 5 13 6 6,4 0 9 17 10 3,5 9 0 8 5 11,13 17 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,(5),k,=5:,0 4 5 12 6 6,4 0 9 16 10 3,5 9 0 8 5 11,12 16 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,1 2 3 5 5 6,1 2 1 5 1 6,1 1 3 4 5 1,5 5 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,1 2 3 3 5,0 4 5 12 6 6,4 0 9 16 10 3,5 9 0 8 5 11,12 16 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,1 2 3 5 5 6,1 2 1 5 1 6,1 1 3 4 5 1,5 5 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,(6),k,=6:,0 4 5 12 6 6,4 0 9 12 10 3,5 9 0 8 5 11,12 12 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,1 2 3 5 5 6,1 2 1 6 1 6,1 1 3 4 5 1,5 6 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,0 4 5 12 6 6,1 2 3 5 5 6,1 2 1 6 1 6,1 1 3 4 5 1,5 6 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,0 4 5 12 6 6,4 0 9 12 10 3,5 9 0 8 5 11,12 12 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,1,2,3,5,6,4,6,5,8,5,4,3,6,7,6,6,9,故从,v,4,到,v,2,的最短路：,途中点,:,v,6,从,v,6,向前追溯：,得,:,v,4,v,6,1 2 3 5 5,0 4 5 12 6 6,4 0 9 12 10 3,5 9 0 8 5 11,12 12 8 0 6 9,6 10 5 6 0 7,6 3 11 9 7 0,1 2 3 5 5 6,1 2 1 6 1 6,1 1 3 4 5 1,5 6 3 4 5 6,1 1 3 4 5 6,1 2 1 4 5 6,1,2,3,5,6,4,6,5,8,5,4,3,6,7,6,6,9,得,:,v,4,v,6,从,v,6,向后追溯：,得,:,v,4,v,6,v,2,0 4 5 12 6 6,floyd,算法的程序实现方法：,(1),输入带权的邻接矩阵：,(2),赋初值：对所有的,i,与,j,，,d,(,i,j,) ,w,(,i,j,),r,(,i,j,),j,k, 1,(3),更新,d,(,i,j,),与,r,(,i,j,),：对所有的,i,与,j,，若,d,(,i,k,)+,d,(,k,j,),d,(,i,j,) ,则,d,(,i,j,) ,d,(,i,k,)+,d,(,k,j,),r,(,i,j,),k,(4),若,k,=,n,停止；否则,k,k,+1,转,(3),floyd算法的程序实现方法：(2)赋初值：对所有的i与j，,例,7.5,出租车的最短行驶路线问题,某地的出租车公司为了更好地服务，向顾客承诺“出租车走最短的行驶路线，方便快捷。”乘客上车后告知司机目的地，出租车电脑就可以计算出到达目的地的最短行驶路线，下图给出该地的交通路线示意图，,要求：,(1),编写用,floyd,算法求,50,个节点中任意两个节点间的最短路径,matlab,函数。,(2),调用所编写的函数，求出从标号为,22,的地点到标号为,44,的地点的最短行驶路线。,例7.5 出租车的最短行驶路线问题,150,7,150 7,function d,path=floydg(a,sp,ep),n=size(a,1);D=a;R=zeros(n);,for j=1:n,R(:,j)=j;,end,for k=1:n,for i=1:n,for j=1:n,if D(i,k)+D(k,j)D(i,j),D(i,j)=D(i,k)+D(k,j); R(i,j)=k;,end,end,end,end,解,(1),function d,path=floydg(a,sp,c0=R(sp,ep);L1=c0;c=c0;,while R(sp,c)=c,c=R(sp,c);L1=c,L1;,end,b=c0;L2=;,while R(b,ep)=ep,b=R(b,ep); L2=L2,b;,end,d=D(sp,ep);,path=sp,L1,L2,ep;,end,c0=R(sp,ep);L1=c0;c=c0;,(2),输入带权的邻接矩阵：,D,命令窗口：,d,path=floydg(D,22,44),d =,2410,path =,Columns 1 through 12,22 24 28 31 33 38 41 42 43 47 45 44,(2) 输入带权的邻接矩阵：D命令窗口：d,path=f,五、最小生成树,问题,树： 连通且不含圈的无向图称为树常用,T,表示,.,树中的边称为树枝,.,树中度为,1,的顶点称为树叶,.,支撑树： 设图,G,(,V,E,),，若,T,是树，,且,称树,T,是图,G,的支撑（生成）树。,最小生成树：赋权连通图,G,的所有支撑树中，其各边权之和最小的支撑树，称为连通图,G,的最小生成树。,解决最小生成树的常用方法：克鲁斯卡尔算法、普利姆算法。,五、最小生成树问题树： 连通且不含圈的无向图称为树常用T表,普利姆（,Prim,）算法：,设置两个集合,P,和,Q,，其中,P,、,Q,分别用于存放最小生成树的顶点和边，,P,的初值为,P,=,v,1,，,Q,的初值为,Q,=,。,普利姆算法的基本思想：从所有,的边中，选取一条具有最小权值的边,uv,，将顶点,v,加入到集合,P,中，将边,uv,加入到集合,Q,中，不断重复下去，直到,P,=,V,中止。,普利姆（Prim）算法： 设置两个集合P和Q,普利姆（,Prim,）算法：,设置两个集合,T,和,Q,，其中,T,、,Q,分别用于存放最小生成树的顶点和边，,T,的初值为,T,=,v,1,，,Q,的初值为,Q,=,。,普利姆算法的基本思想：,从所有 的边,uv,中，,选取一条具有最小权值的边,uv,，,将顶点,v,加入到集合,T,中，再将从集合,S,中剔除，,将边,uv,加入到集合,Q,中，,不断重复下去，直到,T,=,V,中止。,普利姆（Prim）算法： 设置两个集合T和Q,1,2,3,5,6,4,6,5,8,5,4,3,6,7,6,6,9,7,6,4,T=v,2,S=v,1,v,3,v,4,v,5,v,6,v,7,Q=v,2,v,6,Q=v,2,v,6,v,2,v,1,T=v,2,v,6,T=v,2,v,6,v,1,T=v,2,v,6,v,1,v,3,Q=v,2,v,6,v,2,v,1,v,1,v,3,T=v,2,v,6,v,1,v,3,v,5,Q=v,2,v,6,v,2,v,1,v,1,v,3,v,3,v,5,T=v,2,v,6,v,1,v,3,v,5,v,7,T=v,2,v,6,v,1,v,3,v,5,v,7,v,4,最生成小树为,Tree=v,2,v,6,v,2,v,1,v,1,v,3,v,3,v,5,v,6,v,7,v,7,v,4,最小生成树的权为,27,。,例,7.6,求右图的最小生成树,Q=v,2,v,6,v,2,v,1,v,1,v,3,v,3,v,5,v,6,v,7,Q=v,2,v,6,v,2,v,1,v,1,v,3,v,3,v,5,v,6,v,7,v,7,v,4,12356465854367669764T=v2S=v,普利姆（,Prim,）算法的,matlab,实现：,function A,B,Tch=primg(w,a) %w:,权矩阵，,a,：起始点编号,n=length(w);T=a;S=setdiff(1:n,T);A=;B=;L=;,w(w=0)=inf;k1=1;k2=n-1;,while k1n,min=inf;,for m1=1:k1,for m2=1:k2,t=w(T(m1),S(m2);,if tmin,min=t;s1=T(m1);s2=S(m2);,end,end,end,普利姆（Prim）算法的matlab实现：function,T=T,s2;S=setdiff(S,s2);,A=A,s1;B=B,s2;,L=L,min;,k1=length(T);k2=length(S);,end,Tch=sum(L);,end,T=T,s2;S=setdiff(S,s2);,例,7.7,某单位有,10,个下属部门，均不在同一地点办公，为了实现部门之间的资源共享，该单位打算对原有网络进行改造，将所有各部门通过光缆连接组成园区网。根据前期的考察预测，各部门间的光缆连接费用如下表，,试问该单位应如何铺设光纤能使得成本最低，且保证所属单位之间的连通？,例7.7 某单位有10个下属部门，均不在同一地点办公，为了实,clc,clear,w=0,33,51,52,38,61,61,49,53,51;33,0,44,71,48,51,60,50,49,41;51,44,0,66,43,58,62,34,35,55;52,71,66,0,62,56,61,37,49,48;38,48,43,62,0,55,52,40,28,49;61,51,58,56,55,0,53,39,49,49;61,60,62,61,52,53,0,55,50,56;49,50,34,37,40,39,55,0,64,46;53,49,35,49,28,49,50,64,0,48;51,41,55,48,49,49,56,46,48,0,a=input(,输入起始点标号,a=);,A,B,tch=primg(w,a),A =,1 1 5 9 3 8 8 2 9,B =,2 5 9 3 8 4 6 10 7,tch =,335,clc,clearA =,