信息学 图论 最短路径.doc

图的最短路径教学专题图的最短路径授课学时1学时（约50分钟）教学课型新授课授课对象冬令营A层次教学内容和教学目标知识点学习要求了解理解掌握最短路径问题的描述无权图最短路径单源最短路径(边权值非负)Dijkstra算法中贪心策略Dijkstra算法优化任意顶点对间最短路径Floyd算法中动态规划思想图的传递闭包教学重点有权图最短路径教学难点Dijkstra算法设计过程（用flash动画模拟突破难点）教学流程知识点时间分配最短路径问题的引入2分钟无权图最短路径5分钟单源最短路径(边权值非负)15分钟交互讨论：边权值为负时Dijkstra的局限性及改进5分钟任意顶点对间最短路径15分钟图的传递闭包5分钟媒体使用多媒体课件：动画模拟最短路径求解过程教学内容及示例设计意图目前，互联网上有许多网站可用来查找两个地理之间的通路，例如，Google 地图，Baidu 地图等，这些路径查找系统都是用抽象表示国道或省市间的公路，图中的节点表示城市，图中边表示公路路段，边权值表示城市之间的距离，当然也可以表示从某地出发到达目标的时间。例如，从苏州到南京的司机最关心的是：（1） 苏州、南京之间存在通路吗？（2） 如果苏州、南京之间有一条以上通路，哪条路最短？目前，第一个问题我们有解决的办法，采用深度优先搜索或者广度优先搜索遍历图可以达到目的，本节课我们还将讨论其他算法。第二个问题是本节重点讨论的，虽然我们可以枚举任一条可能路径，然后检查是否为最短，但是几乎需要n！的时间，效率太低，我们需要更有效的。一、无权图最短路径例1：如下图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，如果在每一个城市均需要换乘一次飞机，问从C1到其余各城市最少换乘次数。图1 六个城市地图对于图G=（V，E），顶点集合V和边集合E，边没有赋权值，或者也可以认为权值均为1，Ci,j=1，一条路径C1，C2上的边数叫做无权路径长度（Unweighted path length）找出从C1出发到其余各点的最短路径。因为边是没有赋权的，所以只对边的数目感兴趣，如果需要记录实际路径我们可以增加一个变量path来代表路径就可以了。此时此刻可以说从C1到C1（它本身）的最短路径是长为0的路径，把这个信息做个标记，得到下图：图2 C1被访问然后开始寻找所有与C1相连的顶点，它们与C1的距离为1，此时我们可以看到C2、C3与C1仅有“一边之遥”，把它们表示在下图，图3 C1被访问后对邻居顶点的影响以此推断，到算法结束，分别如下图所示：图4 最短路径图显然这种搜索方式就是大家学过的图的广（宽）度优先搜索（Breadth-first search），该方法按层次处理顶点：距开始点最近的顶点首先被访问到，而最远的点最后被访问。伪代码如下：用邻接矩阵存储图/ 无权最短路径/ 输入：图的邻接矩阵ga，源点i/ 输出：源点i至图其它各点的最短路径path（需逆向追溯路径）和长度distprocedure shortest_unweighted(i:integer);begin disti := 0; 其它dist为一个非常大的值代表不可达； pathi :=0; / 0代表是起点或者访问不到；path记录由哪一点访问它 顶点i 进入队列 Q； while 队列Q 非空 dobegin 从队列Q中取出队首元素v； knownv := true; for j := 1 to n do / 依次访问v的所有可直达顶点 begin if ( not knownj ) and ( gav,j =1 ) then begin if distj 为非常大的值then distj := distv + 1; pathj := v; 顶点j 进入队列Q； end; / end of then end ; / end of for end; / end of while end; / end of shortest_unweithted对于每个顶点，我们追踪了三个信息：是否被访问过？距起点的距离是多少，由哪个顶点去访问它下面的一组表格显示追踪过程：注意最开始dist的值均为非常大的值 表 1 追踪过程鉴于两个对顶点集合的循环，该算法的的时间复杂度为O（|V|2）效率较低，这是因为在内部循环中，尽管所有顶点早就known了，但是循环还要继续下去。请大家思考优化方法（提示：使用邻接表存储）。看能否优化到O（|V| + |E|），对于边信息较少的图有很大的速度提升。如果图是赋权图，那么问题就明显地变得困难了，这是因为每个点的重要性不仅仅局限于离起点的远近，而跟它提供的边的权值的有关。不过我们仍然可以使用来自无权情形时的想法。请看下面的讨论二、单源最短路径（从一个顶点到其余各顶点的最短路径，边的权值为非负）例2：如下图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci的最短路径(2i6)，输出路径序列及最短路径的路程长度。图5 赋权六城市地图问题分析下面给出解决这个问题的Dijkstra算法思想。 Dijkstra算法像无权最短路径算法一样，按阶段进行。在每个阶段，Dijkstra算法选择一个顶点Cm，顶点Cm须满足它在所有未访问顶点中具有最小的distm,同时算法声明从Ci到Cm的最短路径是已知的。阶段的其余部分由其它顶点j的dist值的更新工作组成。区别在于：在无权的情形中，若distj=非常大的值（如maxint），则distj=distm+1，而赋权的情形，如果当distj的新值distm + GAm,j是个更好的改进值，我们就让distj=distm + GAm,j，即distj= Mindistj,distm+GAm,j，这是一次松弛操作。简而言之，在通向j路径时，是否使用顶点m由算法来判断。当然原始的distj是没有用到distm的值的。Dijkstra算法瞬间执行图：下一步选择顶点x图6 通过u到达未访问顶点序列中的x路径最短具体算法思路如下：设图G用邻接矩阵的方式存储在GA中，GAi,j=maxint表示Ci，Cj是不关联的，否则为权值（非负值）。设集合S用来保存已求得最短路径的终点序号，初始时S=Ci表示只有源点，以后每求出一个终点Cj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist1.n用来存储当前求得的最短路径，初始时Ci，Cj如果是关联的，则distj等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，distj可能越来越小。再设一个与dist对应的数组path1.n用来存放当前最短路径的边，初始时为Ci到Cj的边，如果不存在边则为空。执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为distm），该元素值就是从源点Ci到终点Cm的最短路径长度，对应的pathm中的顶点或边的序列即为最短路径。接着把Cm并入集合S中，然后以Cm作为新考虑的中间顶点，对S以外的每个顶点Cj，比较distm+GAm,j的distj的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替distj，同时把Cj或边（Cm，Cj）并入到pathj中。从某一个顶点Ci到其余任一顶点Cj的最短路径，可能是它们之间的边（Ci，Cj），也可能是经过k个中间顶点即k+1条边所形成的路径(1kn-2)。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。对于上图，采用Dijkstra算法找出C1到Cj之间的最短路径(2j6)的过程如下：初始时： 表2 初始选择C1123456S100000Dist048maxintmaxintmaxintPathC1C1,C2C1,C3第一次：选择m=2，则S=C1,C2，计算比较dist2+GA2,j与distj的大小 表3 选择C2123456S110000Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：选择m=3，则S=C1,C2,C3，计算比较dist3+GA3,j与distj的大小 表4 选择C3123456S111000Dist04789maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5第三次：选择m=4，S=C1,C2,C3,C4，计算比较dist4+GA4,j与distj的大小 表5 选择C4123456S111100Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6第四次：选择m=5，则S=C1,C2,C3,C4,C5，计算比较dist5+GA5,j与distj的大小 表6 选择C5123456S111110Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因为该图的度n=6，所以执行n-2=4次后结束，最后一个顶点C6如果dist不是maxint，代表有路径，它是不需要探索的。表7 C6为最后顶点123456S111111Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6此时通过dist和path数组可以看出：C1到C2的最短路径为：C1C2，长度为：4；C1到C3的最短路径为：C1C2C3，长度为：7；C1到C4的最短路径为：C1C2C4，长度为：8；C1到C5的最短路径为：C1C2C3C5，长度为：9；C1到C6的最短路径为：C1C2C3C5C6，长度为：13；下面给出具体的Dijkstra算法框架（注：为了实现上的方便，我们用一个一维数组s1.n代替集合S，用来保存已求得最短路径的终点集合，即如果sj=0表示顶点Vj不在集合中，反之，sj=1表示顶点Vj已在集合中）。主要代码如下：/ 无向有权图单源最短路径/ 输入：图的邻接矩阵ga，源点i/ 输出：源点i至图其它各点的最短路径path和长度distProcedure Dijkstra(GA,dist,path,i)； 表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合BeginFor j:=1 To n Do Begin 初始化 If ji Then sj:=0 Else sj:=1； distj:=GAi,j； If distjmaxint maxint为假设的一个足够大的数 Then pathj:=i+jElse pathj:= ； End；For k:=1 To n-2 Do Begin w:=maxint；m:=i； For j:=1 To n Do 求出第k个终点Cm If (sj=0) and (distjw) Then Begin m:=j；w:=distj； End； If mi Then sm:=1 else exit；若条件成立，则把Cm加入到S中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去 For j:=1 To n Do 对sj=0的更优元素作必要修改 If (sj=0) and (distm+GAm,jdistj) Then Begin Distj:=distm+GAm,j；pathj:=pathm+j； End； End；End；请注意，图的邻接矩阵存储中，GAI,j存放边的值，如果边不在图中出现，我们赋予GAI,j一个数值很大的数。这个大数可任选，但需要注意：1）该数值应大于代价矩阵的最大值2）该数值不应该distm+GAm,j的语句溢出。我们来分析一下Dijkstra算法的时间复杂度，对于有n个顶点的图，其复杂度为O（n2）当然如果我们选择更好的数据结构如用邻接表存储图结构，在选择m结点检查distm时采用优先队列那么时间复杂度可以在O(nlogn)时间内，同学们如果感兴趣可以去查阅相关书籍。另外我们要指出的Dijkstra算法，是20世纪中期，Edsger Dijkstra提出的一个非常简单、有效的贪心算法来求解单源最短路径问题。它实际上是一个用于图遍历的广度优先搜索算法的一个“拓展”版本，它每次都选择了一个“领先的”结点。它的出现可能源于下面的生活常识：假设G的边构成一个充满水的管道系统，这个管道在结点处相交，每条边有一定的长度，现在假设在结点S处搅动一下水，并且从S开始引起一个波动。当这个波动以常数速度向外传播时，波面扩张按照它们到S的距离增加的顺序到达结点。一个事实：波面到达任意结点V所走的路径恰好是一条最短路径。对于有向无环图（DAG）同样可以采用上述算法来求单源最短路径，但是如果边权出现负值将无法使用Dijkstra算法，请看下例？使用Dijkstra算法，得到1-3的最短路径为1，而实际上是0。一个诱人的方案是将一个常数加到们每一条边的权值上，如此除去负的边，再计算新图的最短路径问题，然后把结果减去常数后用到原来的图上。这种方案不可能直接实现，因为路径有可能发生变化或者，那些有许多条边的路径变得比那些具有很少条边的路径权值和更重了。如下图 每条边都加上一个正数2边权值 + 2图 7 有负权边对Dijkstra算法影响问题出在哪里？Dijkstra算法中顶点3先于2被声明为已经访问过的定点，1到3的路径不会发生变化，但此时恰好存在了一条可以从未访问的顶点2回到3的负权边，这就有可能导致路径1-2-3比1-3更短，尽管路径1-2比1-3长。这表明了一条路径可以从“昂贵”的边开始，然后接着用“负费用”的边进行补偿，Dijkstra风格的贪心方法在这里不起作用。下面我们来看一种既可以解决边权为负，且可以同时求得任一对顶点间最短路径的算法。三、Floyd算法例3：以例2图为例，求任意一对顶点之间的最短路径。问题分析这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：Floyd算法，它的思路简单，但时间复杂度仍然为O（n3），下面介绍Floyd算法。带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组D，D的初值等于GA。这是因为，如果不允许使用任何中间顶点，Ci到Cj的距离就是GAI,j。令DkI,j表示从Ci到Cj的最短路径，路径中的中间顶点编号不大于k。特别地D的初值记为D0I,j。算法从矩阵D0开始，随后一步一步计算D1,D2,D3,Dn。如果已经得到了Dk-1,接下来计算Dk的方法需要考虑一下两种可能情况：1）对任意一对顶点Ci、Cj，从Ci到Cj且中间顶点编号不大于k的最短路径，如果中间没有顶点编号为k的顶点，那么路径长度就是Dk-1I,j（当然有可能是无路径的）。2）如果上述那条从Ci到Cj的最短路径中包括顶点编号为k的顶点，那么路径一定是一条从Ci到Ck的最短路径再接着一条从Ck到Cj的最短路径，而且这两条子路径中都不含顶点编号大于k-1的顶点，因而它们的长度分别是Dk-1I,k,Dk-1k,j。公式：DkI,j=Min Dk-1I,j，Dk-1I,k + Dk-1k,j, 1kn边界条件D0I,j=GAI,j，（不经过任何一个顶点时路径长度）这是动态规划技术典型的应用之一。Floyd算法需要在D上进行n次运算，每次以Ck（1kn）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，依次运算后，D中的每个元素Di，j就是图G中从顶点Ci到顶点Cj的最短路径长度。再设一个二维数组P1.n,1.n，记录最短路径，其元素类型为集合类型（注意有向图中此数组中只记录了包含顶点）。Floyd算法的具体描述如下：/无向有权图任一顶点对间最短路径/ 输入：图的邻接矩阵ga，源点i/ 输出：任意顶点间的最短路径path和长度distProcedure Floyd(GA，D，P)； Begin For i:=1 To n Do 初始化 For j:=1 To n Do Begin Di,j:=GAi,j； If Di,jmaxint Then pi,j:=i+jElse pi,j:= ； End； For k:=1 To n Do 枚举n个顶点 For i:=1 To n Do For j:=1 To n Do Begin If (i=k)or(j=k)or(i=j) Then Continue； 重复点无需计算，直接进入下一轮循环 If Di,k+Dk,jDi,j Then Begin 更新最短路径长度，并保存 Di,j：= Di,k+Dk,j； Pi,j：= Pi,k+Pk,j； End； End； End；运用Floyd算法，找出任意一对顶点之间的最短路径及其长度。过程如下表格8 Floyd算法执行过程表格9 Dijkstra算法和Floyd算法比较算法名称解决问题算法思想时间复杂度编码复杂度使用限制优化Dijkstra单源最短路径贪心O（n2）复杂边权非负优先队列斐波那契堆Floyd任一点对最短路径动态规划O（n3）简单边权可为负（无负环）但有时，我们可能只是需要了解在图G中是否存在顶点i到顶点j的路径，这个问题称为图的传递闭包问题。四、传递闭包图的传递闭包主要用于计算图的连通性和图中满足条件的连通分支。在一张图中，如何判别任两个顶点之间是否有路，我们介绍一个跟Floyd算法同样思想的Warshall算法。其思想是通过一系列n阶布尔矩阵来构造一个给定的n阶顶点图的传递闭包。R0,R1,Rk-1,Rk,Rn这一系列矩阵从R0开始，R0不允许它的路径中包含任何中间顶点，所以R0就是图的邻接矩阵。Rk表示中间顶点编号不大于k的矩阵。如何从矩阵Rk-1的元素生成矩阵Rk的元素，有下面的公式：Rki,j=Rk-1i,j or Rk-1i,j and Rk-1i,j这就表明：如果一个元素Rk-1i,j是1，那么Rki,j也是1 如果一个元素Rk-1i,j是0，当且仅当矩阵中第i行第k列的元素和第k行第j列的元素都是1，该元素在Rki,j才会变成1用下面的图8所示：图8 传递闭包矩阵图算法实现时只需要把Floyd算法中路径的加法计算，改为逻辑运算即可。五、推荐实例：1)求图9 中带权有向图中每一对顶点间最短路径。（两种方法） 拓展1：把V2到V0的边权值改为-3，求最短路径 拓展2：在拓展1的基础上，将V1到V2的边权值改为-2，能否求出最短路径（提出负环问题） 图 9 带权有向图2）上海世界博览会志愿者问题描述：虽然上海在世界博览会国家展馆之间修筑了天桥，但来到这里的游客还是喜欢走上海世博会的街道，他们总是想知道某两个展馆之间的最短距离，于是志愿者专门回答游客的这个问题，但是由于他们也不可能把这些信息完全记下来，所以总是要向总部询问。你能胜任这个工作吗？输入：第一行两个数n,m（1n100,1m500）表示一共有n个体育馆，有m条询问。接下来一个n*n的矩阵，其中第i行第j列的元素表示展馆