图论读书报告

1、图论读书报告最短路径问题图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及 连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关 系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的哥尼斯堡七桥问题。在哥尼斯堡的普莱格尔河上有七座桥将 河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始，通过每一 座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在 1736 年解决 了这个问题，他用抽像分析法将这个问题化为第一个图论问题 : 即把每一块陆地用 一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于

2、得到 一个“图”。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个 给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和欧拉回路。这项 工作使欧拉成为图论及拓扑学的创始人。最短路径问题是图论解决的典型实际问题之一，可用来解决厂区布局、管路铺 设、线路安装等实际问题。在日常生活中，我们如果需要常常往返A 地区和 B 地区之间，我们最希望知道的可能是从 A 地区到 B 地区间的众多路径中，那一条路径的 路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图 ( 由结点 和路径组成的 )中两结点之间的最短路径。 算法具体的形式包括 : (1) 确定起点的 最短路径问题 :

3、 即已知起始结点，求最短路径的问题。 (2) 确定终点的最短路径问 题: 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向 图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向 反转的确定起点的问题。 (3) 确定起点终点的最短路径问题 : 即已知起点和终点， 求两结点之间的最短路径。(4) 全局最短路径问题 : 求图中所有的最短路径。一、相关定义1.1 图 一集元素及它们之间的某种关系称为图。具体地说，图是一个二元组(V，E) ，其中集合V称为顶点集，集合E是V中元素组成的某些无序对的集合，称为边集。 例:给定G=(V,E)，其中V,v,v,v,v,v

4、 12345E,(v,v),(v,v),(v,v),(v,v),(v,v),(v,v),(v,v) 12233435151555这便定义出一个图。1.2 赋权图对图G的每条边e，赋以一个实数w(e)，称为边e的权。每个边都赋有权的图 称为赋权图。权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运 费、里程或道路的造价等。1.3 最短路径问题给定赋权图G及G中两点u, v，求u到v的具有最小权的路(称为u到v的最 短路)。注：赋权图中路的权也称为路的长，最短(u，v)路的长也称为u, v间的距 离，记为d(u，v)。最短路径问题是图论中的一个基本问题。在赋权图中，每条边 都有一个数值权

5、 (代表其长度、成本、时间等 )，找出两节点之间总权和最小的 路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有 顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义 在于选择合理的中转中心，使得总的费用最少。最短路问题是一个优化问题，属于 网络优化和组合优化的范畴。在图论中最典型的两种求最短路径算法分别是Dijkstra 算法和 Floyd 算法，其中 Dijkstra 算法适用于前者，而 Floyd 算法适用 于后者。二、Dijkstra 算法2.1 Dijkstra 算法Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路

6、 径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。2.2 Dijkstra算法思想Dijkstra 算法思想为：设G=（V,E）是一个带权有向图，把图中顶点集合 V分成 两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源 点，以后每求得一条最短路径，就将 加入到集合S中，直到全部顶点都加入到S 中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最 短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于

7、从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路 径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前 最短路径长度。2.3 Dijkstra算法具体步骤以下面的例子说明如下图，设A为源点，求A到其他各顶点（B、C D E、F）的最短路径。线上 所标注为相邻线段之间的距离，即权值。2算法执行步骤如下表步骤 S 集合中 U 集合中1 选入 A,此时 S= U=此时最短路径 A?A=0 A?B=6， A?C=3，以A为中间点，从A开始找A?其它U中的顶点=?,发现A?C=3权值为最短2选入C,此时S= U=A?C?B=5

8、比上面第一步的A?B=6要短）此时最短路径A?A=0 A?C=3以C为中 间点，此时到D权值更改为A?C?B=5从A?C=3这条最短路径开始找A?C?D=6A?C?E=7，A?C?其它U中的顶点二？，发现A?C?B=5权值为最短3 选入 B,此时 S= U=此时最短路径A?A=0 A?C=3 A?C?B=5 A?C?B?D=1比上面第二步的A?C?D=6S长）以B为中间点此时到D权值更改为A?C?D=6从A?C?B=5这条最短路径开始找A?C?B其它U中的顶点=?，发现A?C?D=6X值为最短 4 选入 D,此时 S= U=此时最短路径A?A=0 A?C=3 A?C?D?E=8比上面第二步的

9、A?C?E=7A?C?B=5 A?C?D=6要长）此时到E权值更改为A?C?E=7A?C?D?F=9以D为中间点，从A?C?D=6条最短路径开始找发现A?C?E=7权值为最短5 选入 E,此时 S= U=此时最短路径A?A=0 A?C=3 A?C?E?F=12比上面第四步的A?C?B=5 A?C?D=6 A?C?E=7 以 EA?C?D?F=长)此时到 F 权值更改为为中间点 A?C?D?F=9从A?C?E=7这条最短路径开始找发现A?C?D?F=9X值为最短6选入F，此时S= U集合已空，查找完毕。此时最短路径 A?A=0， A?C=3，A?C?B=5，A?C?D=，6A?C?E=7， A?

10、C?D?F=9三、Floyd 算法3.1 Floyd 算法的基本思想全部顶点间最短路径算法具有代表性的是 1962年由福劳德 (Floyd) 提出的算 法。他的主要思想是从代表任意 2个顶点v到v的距离的带权邻接矩阵开始，ij每次插入一个顶点v,然后将v到v间的已知最短路径与插入顶点v作为中间 kijk顶点(一条路径中除始点和终点外的其他顶点)时可能产生的v到v路径距离 比 ij 较，取较小值以得到新的距离矩阵，如此循环迭代下去，依次构造出 n 个矩 阵(2)(n)D ，D, ,，D,当所有的顶点均作为任意2个矩阵v到v中间顶点时得 到 ij(n)的最后的带权邻接矩阵D就反映了所有顶点对之间的

11、最短距离信息，成为 图G的距离矩阵。最后对G中各行元素求和值并比较大小，决定单个或多个最佳的 点。3.2Floyd 算法构造距离矩阵的原理对一个有n个顶点的图G将顶点用n个整数(从1到n)进行编号。把G(0)(0)的带权邻接矩阵W作为距离的初值，即D=(d)=W ijn x m(1)(1)(1)(0)(0)(0)第一步构造D=(d)，其中d=min d，d+d是从v到v的只 ijn x m ijiji11jij允许以 v 作为中间点的路径中最短路长度。 1(2)(2)(2)(1)(1)(1)第二步构造D=(d)，其中d=min d，d+d是从v到v的只 ijn x m ijiji22jij允许

12、以 v、v 作为中间点的路径中最短路长度。 1 2(n)(n)(n)(n)(n)(n)第n步构造D=(d)，其中d=min d，d+d是从v到v的只 ijn x m ijijinnjij允许以 v、v、, 、v 作为中间点的路径中最短路长度，即是从 v 到 v 中间可插 12nij(n) 入任何顶点的路径中最短路的长度，因此 D 即是距离矩阵。3.3Floyd 算法具体步骤以下面的例子说明某城市考虑在开发区建立垃圾中转站。在垃圾站的选址问题中，点表示可供选 址的垃圾站，而其间的连线表示运输费用，其需求点之间运费如图所示( 英文字母 为可选垃圾站点，数字为相邻站点之间的运费 ) 。在垃圾中转站的

13、选址中，要求该 中转站到其他站点的距离最短，即运输费用最少，这里通过运用最短路径 Floyd 算 法可以求出该网点布局的最佳中转站。10 b ae d 26(0)(0)首先，确定矩阵D其中若顶点v(编号i)到v(编号j)有边相连，则dijij(0)(0)(0),等于该边边权，否则d=m d=0。由图1写出其初值带权邻接矩阵D: ijii010,4, ，,1003,8 ,(0),3035D(0),(d),ij5，5 ,4,3026, 然后，对 k=1，2，3，, ， n 依次 85260, ，n-1 n利用算法原理中第n步递归公式，由已知的D各元素确定D的各元素值。 插(1)(1)入顶点a后D的

14、各元素和相应的最短路径因为对称性，D的第一行元素和第一(0)(1)列元素与D相同，D的主对角线上的元素均为0,所以只需计算其余6 个元素的值:(1)(0)0(0) d,mind,d， d,min3,10， ,3bcbcbaac(1)(0)0(0) d,mind,d， d,min,10， 4,14bdbdbaad(1)(0)0(0) d,mind,d， d,min8,10， ,8bebebaae(1)(0)0(0) d,mind,d， d,min3,， 4,3cdcdcaad(1)(0)0(0) d,mind,d， d,min5,， ,5cececaae(1)(0)0(0)d,mind,d， d

15、,min26,4， ,26 dededaae010,4, ，,1003148, (1)(1),3035D,(d),ij5， 5, 由此可知， 4143026,85260,，依次插入b，c，d，e，可得不断更新的距离矩阵：01013418， 01013418，,1003681003148,(3)(2)133035133035D,D,463064143022,1885601885220, ，0107410 0107410，,100368100368, ,(5)(4)7303573035D,D, ,4630646306,108560108560,? ? ? ?(5) 最终求得距离矩阵 D 的各元素值就是相应顶点间的最短路径。最后，计算第 i 行各元素值