matlab图与网络分析模型选讲

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,v4 E(G)= e1,e2,e3,e4,e5,e6 e3=(v1,v3) 若图若图G是的边是有方向的，称是的边是有方向的，称G是有向图，有向图的是有向图，有向图的 边称

2、为有向边或弧。边称为有向边或弧。 常用术语常用术语 1)边和它的两端点称为互相边和它的两端点称为互相关联关联. 2)与同一条边关联的两个端点称与同一条边关联的两个端点称 为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3)端点重合为一点的边称为端点重合为一点的边称为环环. 4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边 5)既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 6) 若图若图

3、G的每一条边的每一条边e 都赋以一个实数都赋以一个实数w(e)， 称称w(e)为边为边e的的权权，G连同边上的权称为连同边上的权称为赋权图赋权图 , 记为：记为：G(V,E,W)， W=w(e)| eE v1 v2 v3 v4 5 3 2 7) 图图G的中顶点的个数，的中顶点的个数， 称为图称为图G的阶；图中与某的阶；图中与某 个顶点相关联的边的数目，个顶点相关联的边的数目， 称为该顶点的度。称为该顶点的度。 8）完全图：若无向图的任）完全图：若无向图的任 意两个顶点之间都存在着意两个顶点之间都存在着 一条边，称此图为完全图。一条边，称此图为完全图。 2.图的矩阵表示图的矩阵表示 邻接矩阵邻接

4、矩阵: (以下均假设图为简单图以下均假设图为简单图). 图图G的邻接矩阵是表示顶点之间相邻关系的矩阵：的邻接矩阵是表示顶点之间相邻关系的矩阵： A=(aij)， 0 1 ij a 若若vi与与vj相邻相邻 若若vi与与vj不相邻不相邻 或权值，或权值， 或或， 其中：其中： v1 v2 v3 v4 0010 0011 1101 0110 A v1 v2 v3 v4 5 4 3 1 04 031 4305 150 A 无向图无向图G邻接矩阵邻接矩阵A=(aij) 有向图有向图G邻接矩阵邻接矩阵A=(aij) v1 v2 v3 v4 v1 v2 v3 v4 5 4 3 1 0000 0011 10

5、00 0010 A 0 031 40 50 A 二、最大流问题二、最大流问题 定义：设定义：设G(V,E)为有向图，若在每条边为有向图，若在每条边e上定义一个非上定义一个非 负权负权c，则称图，则称图G为一个网络，称为一个网络，称c为边为边e的容量函数，的容量函数， 记为记为c(e)。 若在有向图若在有向图G(V,E)中有两个不同的顶点中有两个不同的顶点vs与与vt ， 若顶点若顶点vs只有出度没有入度，称只有出度没有入度，称vs为图为图G的源，的源， 若顶点若顶点vt只有入度没有出度，称为只有入度没有出度，称为G的汇，的汇， 若顶点若顶点v 既不是源也不是汇，称为既不是源也不是汇，称为v中间

6、顶点。中间顶点。 v2 v4 v1 v3 vs vt 4 8 3 7 5 7 3 7 v2 v4 v1 v3 vs vt 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)的中间顶点，的中间顶点， Vu vuf),( Vw wvf),(有：有： v2 v4 v1 v3 vs v

7、t 4 8 3 7 5 7 3 7 网络的总流量为从源网络的总流量为从源vs 流出的总流量：流出的总流量： Vw s wvffV),()( 流入汇流入汇vt 总流量：总流量： Vu t vuffV),()( 定义：设网络定义：设网络G(V,E)为相容网络，为相容网络，u,v是是G的相邻顶点，的相邻顶点， G的容量函数为的容量函数为c(u,v)，实际流量函数为，实际流量函数为f(u,v)，vs 和和vt分分 别为别为G(V,E)的源和汇，的源和汇，V(f)为从源为从源vs流出的总流量，流出的总流量， 若：若： Vu uvf),( Vu vuf),( t ts s vvfV vvv vvfV ),

8、( , , 0 ),( 则称该网络称为守恒网络。则称该网络称为守恒网络。 守恒网络中的流守恒网络中的流 f 称为可行流。称为可行流。 若存在一个可行流若存在一个可行流f *，使得对所有可行流，使得对所有可行流 f 都都 有有V(f *) V(f )成立，则称成立，则称f *为最大流。为最大流。 最大流模型：最大流模型： )(maxfV s.t: Vv ij Vv ji jj vvfvvf),(),( ,),(0 ijji cvvf ),(Vvv ji si vvfV ),( Vvvvv itsi , , 0 t vvfV ),( 例例7.1分组交换技术在计算机网络中发挥着重要作用，信分组交换技

9、术在计算机网络中发挥着重要作用，信 息从源节点到目的节点不再需要一条固定的路径，而是息从源节点到目的节点不再需要一条固定的路径，而是 将其分割为几组，通过不同的路径传输到目的节点，目将其分割为几组，通过不同的路径传输到目的节点，目 的节点再重新组合还原文件。现考察如图所示的网络，的节点再重新组合还原文件。现考察如图所示的网络， 图中两节点间的数字表示两交换机间可用的带宽，此时图中两节点间的数字表示两交换机间可用的带宽，此时 从节点从节点1到节点到节点9的最大带宽为多少？的最大带宽为多少？ v2 v5 v1v3 v8 2.5 v9 v4 v7 v6 7.1 3.4 6.1 5.62.4 3.6

10、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=( fij) 记容量矩阵为记容量矩阵为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

11、 0 v2 v5 v1v3 v8 2.5 v9 v4 v7 v6 7.1 3.4 6.1 5.62.4 3.6 3.8 7.4 4.9 5.7 7.2 5.3 4.5 3.8 6.7 7.4 )(maxfV Vu ji Vu ij jj ff 9 ),( 9 , 1 , 0 1 ),( ifV i ifV ,0CF .ts 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(

12、j): f(1,j)=flow; sum(node(j): f(j,9)=flow; for(arc:bnd(0,f,c); )(maxfV Vu ji Vu ij jj ff 9 ),( 9 , 1 , 0 1 ),( ifV i ifV ,0CF .ts 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

13、 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0 0; enddata 该程序运行结果：该程序运行结果： 最大流：最大流：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, v2 v5 v1v3 v8 2.5 v9 v4 v7 v6 7.1 3.4 6.1 5.62.4 3.6 3.8 7.4 4.9 5.7 7.2

14、 5.3 4.5 3.8 6.7 7.4 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

15、,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) 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,flow

16、mat=graphmaxflow(f,1,9) name1(1:9,1)=v; name2=int2str(1:9); name=cellstr(strcat(name1,name2); view(biograph(flowmat,name,ShowWeights,on) 三、三、旅行售货员问题（旅行售货员问题（TSPTSP问题）问题） 一个旅行商，从城市一个旅行商，从城市1出发，要遍访城市出发，要遍访城市1,2,3,n 各一次，最后返回城市各一次，最后返回城市1。若从城市。若从城市i到到j的旅费为的旅费为cij， 问他应按怎样的次序访问这些城市，能使得总旅费问他应按怎样的次序访问这些城市，能

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

18、1，由第，由第i城市进入第城市进入第j城市，且城市，且i j 0，其它，其它 目标函数：目标函数： n i n i ijij xcz 11 min 对规模不大的对规模不大的TSP问题可将其转化为数学规划问题：问题可将其转化为数学规划问题： , 1 1 n i ij x j=1,2,3,n , 1 1 n j ij x i=1,2,3,n 1 2 3 4 5 6 到此得到了一个模型，它是一个指派问题的整数规到此得到了一个模型，它是一个指派问题的整数规 划模型。但以上两个条件对于划模型。但以上两个条件对于TSPTSP来说并不充分，来说并不充分， 仅仅是必要条件。仅仅是必要条件。 例如：例如： 以上

19、两个条件都满足，但它显然不是以上两个条件都满足，但它显然不是TSPTSP的解，的解， 它存在两个子巡回。它存在两个子巡回。 则可以避免产生子巡回。则可以避免产生子巡回。 若在原模型上添加变量若在原模型上添加变量ui ， 并附加下面形式的约束条件：并附加下面形式的约束条件： ，1 nnxuu ijji . 12 nji, 20 nui 目标函数：目标函数： n i n i ijij xcz 11 min s.t： , 1 1 n i ij x , 1 1 n j ij x , 1 nnxuu ijji ,2nji , 20 nui i=2,3,n , 1 , 0 ij x i,j=1,2,3,n

20、 j=1,2,3,n i=1,2,3,n TSP问题的数学规划模型：问题的数学规划模型： 例例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.

21、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 9 1 9 1 min ii ijij

22、 xcz s.t： , 1 9 1 i ij x , 1 9 1 j ij x , 89 ijji xuu , 70 i u , 1 , 0 ij x , ji ),92( ji , ji 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

23、#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); 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.

24、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 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.0

25、00000 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 ei与与vi-1和和vi关联，称关联，称 为图为图G的的 四、最短路四、最短路问题问题 道路与轨道：在图道路与轨道：在图G(V,E)中，设中，设 ttv eevevP 2110 一条道路，一条道路，k为路长，为路长，v0为道路为道路P的起点的起点vt为终点，为终点， 各边相异的道路称为行迹，

26、各边相异的道路称为行迹， 顶点不同且边也不同的道路称为轨道（路径）。顶点不同且边也不同的道路称为轨道（路径）。 最短路问题：对赋权图最短路问题：对赋权图G(V,E,W)，在连接指定，在连接指定 起点起点v0与终点与终点vt的所有轨道的所有轨道P中，寻找一条权数之和中，寻找一条权数之和 最小的轨道。最小的轨道。 ),(),(GEeGVv ii 数学模型：数学模型： 设图设图G(V,E,W), 顶点顶点v0,vtV, 边边 e E ，w(e)为边为边e 的权数，的权数，P(v0,vt)是起点为是起点为v0终点为终点为vt为任意一条轨道，为任意一条轨道， 所有这些轨道的全体记为：所有这些轨道的全体记

27、为：S(P) W(P)为轨道为轨道P(v0,vt)上各边的权数之和，上各边的权数之和， )(min),( )( 0 * PWvvPW PSP t 最短路问题需要求出：最短路问题需要求出： （1）权数之和最小的轨道（）权数之和最小的轨道（2）该轨道的权数之和）该轨道的权数之和 求解此问题的方法有：求解此问题的方法有：Dijkstra算法、算法、floyd算法，遗算法，遗 传算法、模拟退火、蚁群算法等。传算法、模拟退火、蚁群算法等。 Dijkstra算法：（算法具体内容略）算法：（算法具体内容略） 是用来求指定两点是用来求指定两点A与与B之间的最短路的，之间的最短路的， 在在matlab中使用命令

28、中使用命令graphshortestpath实现。实现。 调用格式：调用格式：dist,path=graphshortestpath(DG,A,B) dist： A与与B之间的最短路的长度之间的最短路的长度 path： A与与B之间的最短路的路径之间的最短路的路径 DG：权数邻接矩阵：权数邻接矩阵 由权数邻接矩阵画图的命令：由权数邻接矩阵画图的命令： view(biograph(DG,ShowWeights,on) 例例7.3 某地某地10个点个点v1,v2,v10间的道路连接情况为：间的道路连接情况为： 相邻点相邻点 距离距离 相邻点相邻点 距离距离 相邻点相邻点 距离距离 相邻点相邻点 距

29、离距离 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间的最短路。间的最短路。 clc,clear x=1:8,1:8,1:7,9,4,10; y=2:9,3,5,5:10,4,

30、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.

31、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 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=getedgesb

32、ynodeid(h,get(h.Nodes(path),ID); set(edges,LineColor,0,1,0) set(edges,LineWidth,2) 4.2 5.6 6.5 3.5 6.5 15.2 3.8 5.4 7.6 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 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 dist = 21.4000 path = 1 4 6 8 10 floyd算法：算法： 设图设图G(V,E,W)的权邻接矩阵为：的权邻接矩阵为： 其中其中 当当vi与

33、与vj之间没有边相连时，取之间没有边相连时，取 当当vi与与vj之间有边时，取之间有边时，取 wij 为该边的权。为该边的权。 对于无向图对于无向图G，邻接矩阵，邻接矩阵D0是对称矩阵。是对称矩阵。 nnij dD )( )0( 0 )0( ij d )0( ij d ， ijij wd )0( (3)递推产生一个矩阵序列递推产生一个矩阵序列D0, D1, Dn (4) 为最短路距离矩阵，为最短路距离矩阵， floyd算法的步骤：算法的步骤： （求有（求有n个节点的图的最短路距离矩阵个节点的图的最短路距离矩阵Dn的步骤）的步骤） (1)初值初值k=0， nnij dD )( )0( 0 ( )

34、(1)(1)(1) min,) kkkk ijijikkj dddd nn n ijn dD )( )( )(n ij d为为vi到到vj的最短路的距离。的最短路的距离。 (2)计算计算 建立最短路径矩阵建立最短路径矩阵R的步骤：的步骤： （1） ,)( )0()0( nnij rR jr ij )0( , , )2( )1( )( k ij k ij r k r (1)(1)(1)kkk ijikkj ddd (1)(1)(1)kkk ijikkj ddd (3)递推产生一个矩阵序列递推产生一个矩阵序列R0,R1,Rn (4)矩阵矩阵R=Rn为最短路径矩阵为最短路径矩阵 查找最短路路径的方法

35、：查找最短路路径的方法： 若若 则则 是是点点vi与到点与到点vj最短路径的途中点，最短路径的途中点， 1 )( ar n ij 1 a v (1) 向起点向起点vi与追溯：与追溯： ， 1 )( ar n ij ， 2 )( 1 ar n ia ， 3 )( 2 ar n ia ( ) k n iak ra 得：得： 12 , aaai vvvv k (2) 向终点向终点vj与追溯：与追溯： ， 1 )( ar n ij ， 1 )( 1 br n ja , 2 )( 1 ，br n jb ，jr n jbm )( 得：得： jbbba vvvvv m , 211 (3)点点vi与到点与到点

36、vj最短路路径：最短路路径： jbbbaaai vvvvvvvv mk , 2112 例例7.4 求右图中加权图的求右图中加权图的 任意两点间的最短距离任意两点间的最短距离 与最短路径与最短路径. 1 23 5 6 4 6 5 8 5 4 3 6 7 6 6 9 )0( D , 654321 654321 654321 654321 654321 654321 )0( R 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( D )1( R )0( D 0, 4, 5

37、, , 6, 6 4, 0, , , 3 5, , 0, 8, 5, , 8, 0, 6, 9 6, , 5, 6, 0, 7 6, 3, , 9, 7, 0 ,min )1()1()1()( k kj k ik k ij k ij dddd(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

38、 (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 )1( D 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 ,min )1()1()1()( k kj k ik k ij k ij dddd(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

39、1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 (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( D 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 ,min )1()1()1()( k kj k ik k ij k ij dddd (3) k=3: )3( D 0 4 5 13 6 6 4 0 9 17 10

40、 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 )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 ,min )1()1()1()( k kj k ik k ij k ij dddd (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 1

41、3 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) 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()( k kj k ik k ij k ij dddd(5) k=5: )5( D 0 4 5 1

42、2 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 )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

43、 6 1 2 1 4 5 6 ,min )1()1()1()( k kj k ik k ij k ij dddd(6) k=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 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 )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

44、 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 5 6 0 7 6 3 11 9 7 0 1 23 5 6 4 6 5 8 5 4 3 6 7 6 6 9 故从故从v4到到v2的最短路：的最短路： ,12 )6( 24 d , 6 )6( 24 r途中点途中点:v6 , 6 )6( 46 r从从v6向前追溯：向前追溯： 得得: v4 v6 )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

45、 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 1 23 5 6 4 6 5 8 5 4 3 6 7 6 6 9 得得: v4 v6 从从v6向后追溯：向后追溯： , 2 )6( 62 r 得得: v4 v6 v2 floyd算法的程序实现方法：算法的程序实现方法： (1)输入带权的邻接矩阵：输入带权的邻接矩阵： nn jiwW ),( (2)赋初值：对所有的赋初值：对所有的i与与j，d(i,j) w(i,j), r(i,j)j, k 1 (3)更新更新d(i,j)与与r(i,

46、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) 例例7.5 出租车的最短行驶路线问题出租车的最短行驶路线问题 某地的出租车公司为了更好地服务，向顾客承诺某地的出租车公司为了更好地服务，向顾客承诺“出出 租车走最短的行驶路线，方便快捷。租车走最短的行驶路线，方便快捷。”乘客上车后告乘客上车后告 知司机目的地，出租车电脑就可以计算出到达目的地知司机目的地，出租车电脑就可以计算出到达目的地 的最短行驶路线，下图给出该地的交通路线示意图，的最短行

47、驶路线，下图给出该地的交通路线示意图， 要求：要求：(1)编写用编写用floyd算法求算法求50个节点中任意两个节点个节点中任意两个节点 间的最短路径间的最短路径matlab函数。函数。 (2)调用所编写的函数，求出从标号为调用所编写的函数，求出从标号为22的地点到标号的地点到标号 为为44的地点的最短行驶路线。的地点的最短行驶路线。 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

48、(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=k; end end end end 解解(1) 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 (2) 输入带权的邻接矩阵：输入带权的邻接矩阵：D 命令窗口：命令窗口：d,path=floydg(D,22,44) d = 2410 path = Columns 1 t

49、hrough 12 22 24 28 31 33 38 41 42 43 47 45 44 五、最小生成树五、最小生成树问题问题 1 v 树：树： 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示. 树中的边称为树中的边称为树枝树枝. 树中度为树中度为1的顶点称为的顶点称为树叶树叶. 2 v 3 v 4 v 5 v 支撑树：支撑树： 设图设图G(V,E)，若，若T是树，是树， 且且 称树称树T是图是图G的支撑（生成）树。的支撑（生成）树。 ( )( ), ( )( )E TE G V TV G ， 最小生成树：赋权连通图最小生成树：赋权连通图G的所有支撑树中，其各边的所有

50、支撑树中，其各边 权之和最小的支撑树，称为连通图权之和最小的支撑树，称为连通图G的最小生成树。的最小生成树。 解决最小生成树的常用方法：克鲁斯卡尔算法、普利解决最小生成树的常用方法：克鲁斯卡尔算法、普利 姆算法。姆算法。 普利姆（普利姆（Prim）算法：）算法： 设置两个集合设置两个集合P和和Q，其中，其中P、Q分别用于存放最分别用于存放最 小生成树的顶点和边，小生成树的顶点和边，P的初值为的初值为P=v1，Q的初值为的初值为 Q=。 普利姆算法的基本思想：从所有普利姆算法的基本思想：从所有 的边中，选取一条具有最小权值的边的边中，选取一条具有最小权值的边uv，将顶点，将顶点v加加 入到集合入到集合P中，将边中，将边uv加入到集合加入到集合Q中，不断重复下中，不断重复下 去，直到去，直到P= =V中止。中止。 PVvPu , 普利姆（普利姆（Prim）算法：）算法： 设置两个集合设置两个集合T和和Q，其中，其中T、Q分别用于存放最分别用于存放最 小生成树的顶点和边，小生成树的顶点和边，T的初值为的初值为T=v1，Q的初值为的初值为 Q