matlab图与网络分析模型选讲(1)

1、.1第七章第七章 图与网络分析模型选讲图与网络分析模型选讲一、图论的基本知识一、图论的基本知识1.图的概念图的概念定义定义 图图G(V,E)是指一个二元组是指一个二元组(V(G),E(G)，其中，其中: (1)V(G)=v1,v2, vn是非空有限集，称为是非空有限集，称为顶顶点集点集，(2)E(G)是是V(G)中的元素对中的元素对(vi,vj)组成的集合组成的集合称为称为边集。边集。 图图G： V(G)=v1,v2,v3,v4E(G)= e1,e2,e3,e4,e5,e6e3=(v1,v3).2若图若图G是的边是有方向的，称是的边是有方向的，称G是有向图，有向图的是有向图，有向图的边称为有向

2、边或弧。边称为有向边或弧。常用术语常用术语 边和它的两端点称为互相边和它的两端点称为互相关联关联. 与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点点关联的两条边称为点关联的两条边称为相邻相邻的边的边.3)端点重合为一点的边称为端点重合为一点的边称为环环.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边称为称为重边重边5)既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 v1v2v3v4v5e1e2e3e4e5e6.36) 若图若图G的每一条边的每一条边e 都赋以一个实数都赋以

3、一个实数w(e)，称称w(e)为边为边e的的权权，G连同边上的权称为连同边上的权称为赋权图赋权图 ,记为：记为：G(V,E,W)， W=w(e)| eEv1v2v3v45327) 图图G的中顶点的个数，的中顶点的个数， 称为图称为图G的阶；图中与某的阶；图中与某个顶点相关联的边的数目，个顶点相关联的边的数目，称为该顶点的度。称为该顶点的度。8）完全图：若无向图的任）完全图：若无向图的任意两个顶点之间都存在着一意两个顶点之间都存在着一条边，称此图为完全图。条边，称此图为完全图。.42.图的矩阵表示图的矩阵表示邻接矩阵邻接矩阵: (以下均假设图为简单图以下均假设图为简单图). 图图G的邻接矩阵是表

4、示顶点之间相邻关系的矩阵：的邻接矩阵是表示顶点之间相邻关系的矩阵： A=(aij)， 01ija若若vi与与vj相邻相邻若若vi与与vj不相邻不相邻或权值，或权值，或或，其中：其中：.5v1v2v3v4 0010001111010110Av1v2v3v45431 040314305150A无向图无向图G邻接矩阵邻接矩阵A=(aij).6有向图有向图G邻接矩阵邻接矩阵A=(aij)v1v2v3v4v1v2v3v45431 0000001110000010A 00314050A.7二、最大流问题二、最大流问题定义：设定义：设G(V,E)为有向图，若在每条边为有向图，若在每条边e上定义一个非上定义一

5、个非负权负权c，则称图，则称图G为一个网络，称为一个网络，称c为边为边e的容量函数，的容量函数，记为记为c(e)。若在有向图若在有向图G(V,E)中有两个不同的顶点中有两个不同的顶点vs与与vt ，若顶点若顶点vs只有出度没有入度，称只有出度没有入度，称vs为图为图G的源，的源，若顶点若顶点vt只有入度没有出度，称为只有入度没有出度，称为G的汇，的汇，若顶点若顶点v 既不是源也不是汇，称为既不是源也不是汇，称为v中间顶点。中间顶点。v2v4v1v3vsvt48375737.8v2v4v1v3vsvt48375737设设u,v网络网络G(V,E)的相邻顶点，边的相邻顶点，边(u,v)上的函数上的

6、函数f(u,v)称为边称为边(u,v)上的实际流量；上的实际流量；若对网络若对网络G(V,E)的任意相邻顶点的任意相邻顶点u,v 均成立：均成立： 0 f(u,v) c(u,v) ， 称该网络为相容网络。称该网络为相容网络。若若v为网络为网络G(V,E)的中间顶点，的中间顶点， Vuvuf),( Vwwvf),(有：有：.9v2v4v1v3vsvt48375737网络的总流量为从源网络的总流量为从源vs 流出的总流量：流出的总流量： VwswvffV),()(流入汇流入汇vt 总流量：总流量： VutvuffV),()(.10定义：设网络定义：设网络G(V,E)为相容网络，为相容网络，u,v是

7、是G的相邻顶点，的相邻顶点， G的容量函数为的容量函数为c(u,v)，实际流量函数为，实际流量函数为f(u,v)，vs 和和vt分分别为别为G(V,E)的源和汇，的源和汇，V(f)为从源为从源vs流出的总流量，流出的总流量，若：若： Vuuvf),( Vuvuf),( ttssvvfVvvvvvfV ),(, , 0 ),(则称该网络称为守恒网络。则称该网络称为守恒网络。守恒网络中的流守恒网络中的流 f 称为可行流。称为可行流。 若存在一个可行流若存在一个可行流f *，使得对所有可行流，使得对所有可行流 f 都都有有V(f *) V(f )成立，则称成立，则称f *为最大流。为最大流。.11最

8、大流模型：最大流模型：)(maxfVs.t: VvijVvjijjvvfvvf),(),(,),(0ijjicvvf ),(Vvvji sivvfV ),(Vvvvvitsi , , 0tvvfV ),(.12例例7.1分组交换技术在计算机网络中发挥着重要作用，信分组交换技术在计算机网络中发挥着重要作用，信息从源节点到目的节点不再需要一条固定的路径，而是息从源节点到目的节点不再需要一条固定的路径，而是将其分割为几组，通过不同的路径传输到目的节点，目将其分割为几组，通过不同的路径传输到目的节点，目的节点再重新组合还原文件。现考察如图所示的网络，的节点再重新组合还原文件。现考察如图所示的网络，图中

9、两节点间的数字表示两交换机间可用的带宽，此时图中两节点间的数字表示两交换机间可用的带宽，此时从节点从节点1到节点到节点9的最大带宽为多少？的最大带宽为多少？v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.4.13设设fij为从为从vi到到vj的实际流量，得一个的实际流量，得一个9阶方阵：阶方阵：F=( fij)记容量矩阵为记容量矩阵为C =0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00

10、 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0 v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.4.14)(maxfV VujiVuijjjff 9 ),(9 , 1 , 01 ),(ifViifV,0CF .ts.15sets: node/1.9/;arc(node,node):c,f;EndsetsOBJmax=flow;for(node(i)|i

11、#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);)(maxfV VujiVuijjjff 9 ),(9 , 1 , 01 ),(ifViifV,0CF .ts.16data:c=0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0

12、3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0;enddata.17该程序运行结果：该程序运行结果：最大流：最大流：14.2F(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,v2v5v1v3v82.5v9v4v7v67.13.46.15.62

13、.43.63.87.44.95.77.25.34.53.86.77.4.180 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 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

14、,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).19clc,clearx=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,

15、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).20三、三、旅行售货员问题（旅行售货员问题（TSPTSP问题）问题） 一个旅行商，从城市一个旅行商，从城市1出发，要遍访城市出发，要遍访城市1,2,3,n各一次，最后返回城市各一次，最后返回城市1。若从城市。若从城市i到到j的旅费为的旅费为cij， 问他应按怎样的次序访问这些城市，能使得总旅费问他应按怎样的次序访问这些城

16、市，能使得总旅费最少？最少？ 用图论语言描述：在赋权图中，寻找一条经过所有用图论语言描述：在赋权图中，寻找一条经过所有节点，并回到原点的最短路。节点，并回到原点的最短路。 包含图包含图G的每个顶点的路称为哈密顿路；闭的哈密的每个顶点的路称为哈密顿路；闭的哈密顿路称为哈密顿圈。顿路称为哈密顿圈。 到目前为止，到目前为止，TSP问题还没有有效解决方法，现有问题还没有有效解决方法，现有的方法都是寻找近似最优的哈密顿圈，常用方法有边的方法都是寻找近似最优的哈密顿圈，常用方法有边替换法、遗传算法、模拟退火法、蚁群算法等。替换法、遗传算法、模拟退火法、蚁群算法等。.21引入引入0-1变量：变量：xij=1

17、，由第，由第i城市进入第城市进入第j城市，且城市，且i j0，其它，其它 目标函数：目标函数： niniijijxcz11min对规模不大的对规模不大的TSP问题可将其转化为数学规划问题：问题可将其转化为数学规划问题：, 11 niijx j=1,2,3,n, 11 njijx i=1,2,3,n.22123456到此得到了一个模型，它是一个指派问题的整数规到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于划模型。但以上两个条件对于TSPTSP来说并不充分，来说并不充分，仅仅是必要条件。仅仅是必要条件。例如：例如：以上两个条件都满足，但它显然不是以上两个条件都满足，但它显然

18、不是TSPTSP的解，的解，它存在两个子巡回。它存在两个子巡回。则可以避免产生子巡回。则可以避免产生子巡回。若在原模型上添加变量若在原模型上添加变量ui ，并附加下面形式的约束条件：并附加下面形式的约束条件：，1 nnxuuijji. 12 nji, 20 nui.23目标函数：目标函数： niniijijxcz11min s.t：, 11 niijx, 11 njijx, 1 nnxuuijji,2nji , 20 nui i=2,3,n, 1 , 0 ijx i,j=1,2,3,n j=1,2,3,n i=1,2,3,nTSP问题的数学规划模型：问题的数学规划模型：.24例例7.2 (TS

19、P问题问题) 已知已知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,

20、 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 91 2 3 4 5 6 7 8 9.25 9191miniiijijxcz s.t：, 191 iijx, 191 jijx, 89 ijjixuu, 70 iu, 1 , 0 ijx ,

21、ji ),92( ji, ji i,j=1,2,3,nsets: 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);.26

22、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,

23、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.27Objective value: 49.10000X( 1, 4) 1.000000X( 2, 1) 1.000000 X( 3, 2) 1.000000X( 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 按如下次序：按

24、如下次序： 1,4,5,8,9,7,6,3,2,1 访问这些城市时总访问这些城市时总费用最小，最小费费用最小，最小费用：用：49.1.28 ei与与vi-1和和vi关联，称关联，称 为图为图G的的四、最短路四、最短路问题问题道路与轨道：在图道路与轨道：在图G(V,E)中，设中，设ttveevevP2110 一条道路，一条道路，k为路长，为路长，v0为道路为道路P的起点的起点vt为终点，为终点，各边相异的道路称为行迹，各边相异的道路称为行迹，顶点不同且边也不同的道路称为轨道（路径）。顶点不同且边也不同的道路称为轨道（路径）。 最短路问题：对赋权图最短路问题：对赋权图G(V,E,W)，在连接指定，

25、在连接指定起点起点v0与终点与终点vt的所有轨道的所有轨道P中，寻找一条权数之和中，寻找一条权数之和最小的轨道。最小的轨道。),(),(GEeGVvii .29数学模型：数学模型： 设图设图G(V,E,W), 顶点顶点v0,vtV, 边边 e E ，w(e)为边为边e的权数，的权数，P(v0,vt)是起点为是起点为v0终点为终点为vt为任意一条轨道，为任意一条轨道，所有这些轨道的全体记为：所有这些轨道的全体记为：S(P)W(P)为轨道为轨道P(v0,vt)上各边的权数之和，上各边的权数之和，)(min),()(0*PWvvPWPSPt 最短路问题需要求出：最短路问题需要求出：（1）权数之和最小

26、的轨道（）权数之和最小的轨道（2）该轨道的权数之和）该轨道的权数之和求解此问题的方法有：求解此问题的方法有：Dijkstra算法、算法、floyd算法，遗算法，遗传算法、模拟退火、蚁群算法等。传算法、模拟退火、蚁群算法等。.30Dijkstra算法：（算法具体内容略）算法：（算法具体内容略） 是用来求指定两点是用来求指定两点A与与B之间的最短路的，之间的最短路的， 在在matlab中使用命令中使用命令graphshortestpath实现。实现。调用格式：调用格式：dist,path=graphshortestpath(DG,A,B) dist： A与与B之间的最短路的长度之间的最短路的长度

27、path： A与与B之间的最短路的路径之间的最短路的路径 DG：权数邻接矩阵：权数邻接矩阵由权数邻接矩阵画图的命令：由权数邻接矩阵画图的命令： view(biograph(DG,ShowWeights,on).31例例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.645: 5.1 ， 46: 5.1， 47:

28、8.8， 48: 12.356: 4.7 ， 57: 5.2， 59: 7.667: 6.3， 68: 3.9， 69: 5.278: 6.9， 79: 3.5， 710: 6.389: 6.8， 810: 5.9，910: 5.8 求由求由v1到到v10间的最短路。间的最短路。.32clc,clearx=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

29、.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.645: 5.1 ， 46: 5.1， 47: 8.8， 48: 12.356: 4.7 ， 57: 5.2， 59: 7.667: 6.3， 68: 3.9， 69: 5.278: 6.9， 79: 3.5， 710: 6.389: 6.8， 810: 5.9，910: 5.8 .33W=sparse(x,y,w

30、);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) .34 4.2 5.6 6.5 3.5 6.5 15.2 3.8 5.4 7.6

31、 5.1 5.1 8.8 12.3 4.7 5.2 7.6 6.3 3.9 5.2 6.9 3.5 6.3 6.8 5.9 5.8 v1v2v3v4v5v6v7v8v9v10dist = 21.4000path = 1 4 6 8 10.35floyd算法：算法：设图设图G(V,E,W)的权邻接矩阵为：的权邻接矩阵为：其中其中 当当vi与与vj之间没有边相连时，取之间没有边相连时，取 当当vi与与vj之间有边时，取之间有边时，取 wij 为该边的权。为该边的权。对于无向图对于无向图G，邻接矩阵，邻接矩阵D0是对称矩阵。是对称矩阵。 nnijdD )()0(0)0(ijd )0(ijd，ijij

32、wd )0(.36(3)递推产生一个矩阵序列递推产生一个矩阵序列D0, D1, Dn(4) 为最短路距离矩阵，为最短路距离矩阵，floyd算法的步骤：算法的步骤：（求有（求有n个节点的图的最短路距离矩阵个节点的图的最短路距离矩阵Dn的步骤）的步骤）(1)初值初值k=0，nnijdD )()0(0( )(1)(1)(1)min,)kkkkijijikkjddddnnnijndD )()()(nijd为为vi到到vj的最短路的距离。的最短路的距离。(2)计算计算.37建立最短路径矩阵建立最短路径矩阵R的步骤：的步骤：（1） ,)()0()0(nnijrR jrij )0( , )2()1()(ki

33、jkijrkr(1)(1)(1)kkkijikkjddd(1)(1)(1)kkkijikkjddd(3)递推产生一个矩阵序列递推产生一个矩阵序列R0,R1,Rn(4)矩阵矩阵R=Rn为最短路径矩阵为最短路径矩阵.38查找最短路路径的方法：查找最短路路径的方法：若若 则则 是是点点vi与到点与到点vj最短路径的途中点，最短路径的途中点，1)(arnij 1av(1) 向起点向起点vi与追溯：与追溯：，1)(arnij ，2)(1arnia ， 3)(2arnia ( )kniakra 得：得：12,aaaivvvvk(2) 向终点向终点vj与追溯：与追溯：，1)(arnij ，1)(1brnja

34、 ,2)(1，brnjb ，jrnjbm )(得：得：jbbbavvvvvm,211(3)点点vi与到点与到点vj最短路路径：最短路路径：jbbbaaaivvvvvvvvmk,2112.39例例7.4 求右图中加权图的求右图中加权图的任意两点间的最短距离任意两点间的最短距离与最短路径与最短路径. 12356465854367669 )0(D,654321654321654321654321654321654321 )0( R0, 4, 5, , 6, 64, 0, , , 35, , 0, 8, 5, , 8, 0, 6, 96, , 5, 6, 0, 76, 3, , 9, 7, 0.40

35、)1(D )1(R )0(D0, 4, 5, , 6, 64, 0, , , 35, , 0, 8, 5, , 8, 0, 6, 96, , 5, 6, 0, 76, 3, , 9, 7, 0,min)1()1()1()( kkjkikkijkijdddd(1) k=1: 0, 4, 5, , 6, 64, 0, 9, ,10, 35, 9, 0, 8, 5, 11, 8, 0, 6, 96, 10, 5, 6, 0, 76, 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

36、 6(0)R 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.41 )1(D0, 4, 5, , 6, 64, 0, 9, ,10, 35, 9, 0, 8, 5, 11, 8, 0, 6, 96, 10, 5, 6, 0, 76, 3, 11, 9, 7, 0,min)1()1()1()( kkjkikkijkijdddd(2) k=2: 得得: ,)1()2()1()2(RRDD )1(R 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

37、 4 5 6 1 2 1 4 5 6.42(2)R 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 )2(D0, 4, 5, , 6, 64, 0, 9, ,10, 35, 9, 0, 8, 5, 11, 8, 0, 6, 96, 10, 5, 6, 0, 76, 3, 11, 9, 7, 0,min)1()1()1()( kkjkikkijkijdddd(3) k=3: )3(D 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

38、5 6 0 7 6 3 11 9 7 0 )3(R 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.43,min)1()1()1()( kkjkikkijkijdddd(4) k=4: 得得: ,)3(4)()3()4(RRDD )3(R 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 )3(D 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

39、 10 5 6 0 7 6 3 11 9 7 0.44(4)R 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(4)D 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,min)1()1()1()( kkjkikkijkijdddd(5) k=5: )5(D 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

40、6 3 11 9 7 0 )5(R 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.45 )5(D 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 )5(R 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,min)1()1()1()( kkjkikkijkijdddd(6) k=6: )6(D

41、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 )6(R 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.46 )6(R 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 )6(D 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

42、 5 6 0 7 6 3 11 9 7 012356465854367669故从故从v4到到v2的最短路：的最短路： ,12)6(24 d, 6)6(24 r途中点途中点:v6 , 6)6(46 r从从v6向前追溯：向前追溯： 得得: v4 v6 .47 )6(D 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 )6(R 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 612356465854

43、367669得得: v4 v6 从从v6向后追溯：向后追溯： , 2)6(62 r得得: v4 v6 v2.48floyd算法的程序实现方法：算法的程序实现方法：(1)输入带权的邻接矩阵：输入带权的邻接矩阵：nnjiwW ),(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停止；否则停止；否则kk+1 转转(3).49例例7.5 出租车的最短行

44、驶路线问题出租车的最短行驶路线问题某地的出租车公司为了更好地服务，向顾客承诺某地的出租车公司为了更好地服务，向顾客承诺“出出租车走最短的行驶路线，方便快捷。租车走最短的行驶路线，方便快捷。”乘客上车后告乘客上车后告知司机目的地，出租车电脑就可以计算出到达目的地知司机目的地，出租车电脑就可以计算出到达目的地的最短行驶路线，下图给出该地的交通路线示意图，的最短行驶路线，下图给出该地的交通路线示意图，要求：要求：(1)编写用编写用floyd算法求算法求50个节点中任意两个节点个节点中任意两个节点间的最短路径间的最短路径matlab函数。函数。(2)调用所编写的函数，求出从标号为调用所编写的函数，求出

45、从标号为22的地点到标号的地点到标号为为44的地点的最短行驶路线。的地点的最短行驶路线。.50150 7 .51function d,path=floydg(a,sp,ep)n=size(a,1);D=a;R=zeros(n);for j=1:n R(:,j)=j;endfor 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 endend解解(1).52c0=R(sp,ep);L1=c0;c=c0;while R(sp,c)=c c=R(sp,c);L1=c,L1;

46、endb=c0;L2=;while R(b,ep)=ep b=R(b,ep); L2=L2,b;endd=D(sp,ep);path=sp,L1,L2,ep;end.53(2) 输入带权的邻接矩阵：输入带权的邻接矩阵：D命令窗口：命令窗口：d,path=floydg(D,22,44)d = 2410path = Columns 1 through 12 22 24 28 31 33 38 41 42 43 47 45 44 .54五、最小生成树五、最小生成树问题问题1v树：树： 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示.树中的边称为树中的边称为树枝树枝. 树中度为

47、树中度为1的顶点称为的顶点称为树叶树叶. 2v3v4v5v支撑树：支撑树： 设图设图G(V,E)，若，若T是树，是树，且且称树称树T是图是图G的支撑（生成）树。的支撑（生成）树。 ( )( ), ( )( )E TE G V TV G ，最小生成树：赋权连通图最小生成树：赋权连通图G的所有支撑树中，其各边的所有支撑树中，其各边权之和最小的支撑树，称为连通图权之和最小的支撑树，称为连通图G的最小生成树。的最小生成树。解决最小生成树的常用方法：克鲁斯卡尔算法、普利解决最小生成树的常用方法：克鲁斯卡尔算法、普利姆算法。姆算法。.55普利姆（普利姆（Prim）算法：）算法： 设置两个集合设置两个集合P

48、和和Q，其中，其中P、Q分别用于存放最分别用于存放最小生成树的顶点和边，小生成树的顶点和边，P的初值为的初值为P=v1，Q的初值为的初值为Q=。 普利姆算法的基本思想：从所有普利姆算法的基本思想：从所有的边中，选取一条具有最小权值的边的边中，选取一条具有最小权值的边uv，将顶点，将顶点v加加入到集合入到集合P中，将边中，将边uv加入到集合加入到集合Q中，不断重复下去，中，不断重复下去，直到直到P= =V中止。中止。PVvPu ,.56普利姆（普利姆（Prim）算法：）算法： 设置两个集合设置两个集合T和和Q，其中，其中T、Q分别用于存放最分别用于存放最小生成树的顶点和边，小生成树的顶点和边，T的初值为的初值为T=v1，Q的初值为的初值为Q=。普利姆算法的基本思想：普利姆算法的基本思想：从所有