最短路径问题的求解.ppt

《最短路径问题的求解.ppt》由会员分享，可在线阅读，更多相关《最短路径问题的求解.ppt（25页珍藏版）》请在三一办公上搜索。

1、最短路径问题的求解,最短路径是图论中的一个重要问题，具有很高的实用价值，也是信息学竞赛中常见的一类中等难度的题目，这类问题很能联系实际，考察学生的建模能力，反映出学生的创造性思维，因为有些看似跟最短路径毫无关系的问题，也可以归结为最短路径问题来求解。,在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。,一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。,对于不带权的图，只要

2、人为的把每条边加上权值1，即可当作带权图一样处理了。,最短路径问题的求解,例1、假设A、B、C、D、E各个城市之间旅费如下图红色数字所示。某人想从城市A出发游览各城市一遍，而所用旅费最少，试编程输出结果。,问题分析 解这类问题时，很多同学往往不得要领，采用穷举法把所有可能的情况全部列出，再找出其中旅费最少的那条路径；或者采用递归（深搜）找出所有路径，再找出旅费最少的那条。但这两种方法都是费时非常多的解法，如果城市数目多的话则很可能要超时了。实际上我们知道，递归（深搜）之类的算法一般用于求所有解问题（例如求从A出发每个城市都要走一遍一共有哪几种走法？），所以这些算法对于求最短路径这类最优解问题显

3、然是不合适的。,首先，对于这类图，我们都应该先建立一个邻接矩阵，存放任意两点间的数据（如距离、费用、时间等），以便在程序中方便调用，以下介绍几种常见的、更好的求最短路径问题的算法。,最短路径问题的求解,一、宽度优先搜索宽搜也并不是解决这类问题的优秀算法，这里只是简单介绍一下算法思路，为后面的优秀算法做个铺垫。具体如下：1、从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其旅费；2、再次由AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然由AD可以展开得到ADB、ADC、ADE，由A

4、E可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其旅费；3、再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED、AEDB、AEDC，每个结点也需记录下其旅费；4、再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、AEDBC、AEDCB，每个结点也需记录下其旅费；5、到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目的解了。由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少的那条，显而易见也是一种很费时的算法。,最短路径问题的求解,二、启发式搜索在宽度优先搜索算法的基础上

5、，每次并不是把所有可展开的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能越快找到答案。这种算法实现起来并不难，只不过难在找准估价函数，大家可以自已找相关资料学习和思考。,最短路径问题的求解,三、等代价搜索法等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数

6、，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是：1、从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其旅费（括号中的数字）；2、把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开；3、再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开；4

7、、再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点，；5、每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。,最短路径问题的求解,小结：由上可见，启发式搜索和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。,最短路径问题的求解,例2、题目基本同例1，现在把权定义成

8、距离，现在要求A点到E点的最短路径，但并不要求每个城市都要走一遍。,例1、假设A、B、C、D、E各个城市之间旅费如下图红色数字所示。某人想从城市A出发游览各城市一遍，而所用旅费最少，试编程输出结果。,问题分析既然不要求每个点都要走一遍，只要距离最短即可，那么普通的宽度优先搜索已经没有什么意义了，实际上就是穷举。那么等代价搜索能不能再用在这题上呢？答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。是不是搜索到一个结点是以E结束时就停止呢？显然不对。那么是不是要把所有以E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。实际上，应该是搜索到：当我们确定将要展开的

9、某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是E时，这个结点就是我们所要求的答案！因为比这个结点大的点再展开得到的解显然不可能比这个结点优！那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍这种求最短路径问题的其它几种成熟算法。,最短路径问题的求解,四、宽度优先搜索+剪枝 搜索之所以低效，是因为在搜索过程中存在着大量的重复和不必要的搜索。因此，提高搜索效率的关键在于减少无意义的搜索。假如在搜索时已经搜出从起点A到点B的某一条路径的长度是X，那么我们就可以知道，从A到B的最短路径长度必定X，因此，其他从A到B的长度大于或等于X的路径可以一律剔除。具体实现时，可以开一个数组h

10、1.n，n是结点总数，hi表示从起点到结点i的最短路径长度。算法流程如下：1、初始化：将起点start入队，hstart:=0，hk:=maxlongint(1=k=n，且kstart)。2、repeat 取出队头结点赋给t；while t有相邻的结点没被扩展 begin t扩展出新的结点newp；如果 ht+wt,newp hnewp，则将newp入队，把hnewp的值更新为ht+wt,newp；End until 队列空；,最短路径问题的求解,五、迭代法 该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个

11、。即：Dij=min Dij,Dik+Dkj，1Dk+gk,j then begin Dj:=Dk+gk,j;c:=true;end;Until not c；这种算法是产生这样一个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。,最短路径问题的求解,六、动态规划 动态规划算法已经成为了许多难题的首选算法。某些最短路径问题也可以用动态规划来解决，通常这类最短路径问题所对应的图必须是有向无回路图。因为如果存在回路，动态规划的无后效性就无法满足。我们知道，动态规划算法与递归算法的不同之处在于

12、它们的算法表达式：递归：类似f(n)=x1*f(n-1)+x2*f(n-2)，即可以找到一个确定的关系的表达式；动态规划：类似f(n)=min(f(n-1)+x1,f(n-2)+x2)，即我们无法找到确定关系的表达式，只能找到这样一个不确定关系的表达式，f(n)的值是动态的，随着f(n-1),f(n-2)等值的改变而确定跟谁相关。为了给问题划分阶段，必须对图进行一次拓扑排序，然后按照拓扑排序的结果来动态规划。譬如，有如下两个有向图：,最短路径问题的求解,右图因为存在回路而不能用动态规划。而左图是无回路的，所以可以用动态规划解决。对左图拓扑排序，得到的序列是A、B、D、C、E。设F(E)表示从A

13、到E的最短路径长度，然后按照拓扑序列的先后顺序进行动态规划：F(A)=0 F(B)=min F(A)+3=3 F(D)=min F(A)+8,F(B)+2=5 F(C)=min F(B)+9,F(D)+5=10 F(E)=min F(D)+1,F(C)+4=6总的式子是：F(i)=min F(k)+dis(i,k)，k与i必须相连，且在拓扑序列中，k在i之前。,最短路径问题的求解,七、标号法标号法是一种非常直观的求最短路径的算法，单从分析过程来看，我们可以用一个数轴简单地表示这种算法：1、以A点为0点，展开与其相邻的点，并在数轴中标出。,2、因为C点离起点A最近，因此可以断定C点一定是由A直接

14、到C点这条路径是最短的（因为A、C两点间没有其它的点，所以C点可以确定是由A点直接到达为最短路径）。因而就可以以已经确定的C点为当前展开点，展开与C点想连的所有点A、B、D、E。,3、由数轴可见，A与A点相比，A点离原点近，因而保留A点，删除A点，相应的，B、B点保留B点，D、D保留D，E、E保留E，得到下图：,最短路径问题的求解,4、此时再以离原点最近的未展开的点B联接的所有点，处理后，再展开离原点最近未展开的D点，处理后得到如下图的最终结果：,5、由上图可以得出结论：点C、B、D、E就是点A到它们的最短路径（注意：这些路径并不是经过了所有点，而是只经过了其中的若干个点，而且到每一个点的那条

15、路径不一定相同）。因而A到E的最短距离就是13。至于它经过了哪几个点大家可在上述过程中加以记录即可。,最短路径问题的求解,八、Dijkstra算法（从一个顶点到其余各顶点的最短路径，单源最短路径）,例3、如下图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci的最短路径(2i6)，输出路径序列及最短路径的路程长度。,最短路径问题的求解,问题分析 对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的

16、路径(1kn-2)。下面给出解决这个问题的Dijkstra算法思想。,设图G用邻接矩阵的方式存储在GA中，GAi,j=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=Vi表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist1.n用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则distj等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，distj可能越来越小。再设一个与dist对应的数组path1.n用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存

17、在边则为空。,执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为distm），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的pathm中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较distm+GAm,j的distj的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替distj，同时把Vj或边（Vm，Vj）并入到pathj中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保

18、存着相应的最段路径。,对于上图，采用Dijkstra算法找出C1到Ci之间的最短路径(2i6)的过程如下：,最短路径问题的求解,初始时：,第一次：选择m=2，则S=C1,C2，计算比较dist2+GA2,j与distj的大小,第二次：选择m=3，则S=C1,C2,C3，计算比较dist3+GA3,j与distj的大小,第三次：选择m=4，S=C1,C2,C3,C4，计算比较dist4+GA4,j与distj的大小,最短路径问题的求解,第四次：选择m=5，则S=C1,C2,C3,C4,C5，计算比较dist5+GA5,j与distj的大小,因为该图的度n=6，所以执行n-2=4次后结束，此时通过

19、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已在集合中）。Procedure Dijkstra(GA,dist,path,i)；表示

20、求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合 Begin For j:=1 To n Do Begin 初始化 If ji Then sj:=0 Else sj:=1；distj:=GAi,j；If distjmaxint Then pathj:=i+j Else pathj:=；End；,最短路径问题的求解,For k:=1 To n-2 Do Begin w:=maxint；m:=i；For j:=1 To n Do 求出第k个终点Vm If(sj=0)and(distji Then sm:=1 else exit；若条

21、件成立，则把Vm加入到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；,最短路径问题的求解,九、Floyd算法例4、求任意一对顶点之间的最短路径。,问题分析 这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：Floyd算法，它的思路简单，但

22、时间复杂度仍然为O（n3），下面介绍Floyd算法。设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组A，A的初值等于GA。Floyd算法需要在A上进行n次运算，每次以Vk（1kn）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素Ai，j就是图G中从顶点Vi到顶点Vj的最短路径长度。再设一个二维数组P1.n,1.n，记录最短路径，其元素类型为集合类型set of 1.n。Floyd算法的具体描述如下：,最短路径问题的求解,Procedure Floyd(GA，A，P)；Begin For i:=1

23、 To n Do 最短路径长度数组和最短路径数组初始化 For j:=1 To n Do Begin Ai,j:=GAi,j；If Ai,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 Ai,k+Ak,jAi,j Then Begin 找到更短路径、保存 Ai,j：=Ai,k+Ak,j；Pi,j：=Pi,k+Pk,j；End；End；End

24、；,最短路径问题的求解,总结与思考：最短路径问题的求解还不止这几种算法，比如还有分枝定界等等，而且大家也可以创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需要对该种算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。在学习完最短路径后，有没有人想到：能不能修改这些算法，实现求最长路径的问题呢？这种发散性的思维是值得称赞的，对于不存在回路的有向图，这种算法是可行的。但需要提醒的是：如果有向图出现了回路，按照最长路径的思想和判断要求，则计算可能沿着回路无限制的循环下去。这就引出了一个问题：如何判断

25、一个有向图中是否存在回路？可以用bfs或dfs在搜的过程检查这个点是否在前面出现过；当然也可以用拓扑排序算法。,最短路径问题的求解,SERCOI工程组是一个讲究效率的工程小组。为了规划和管理的方便，他们将一个工程分为若干个项目，每个项目都可以独立进行。所有项目都工作完毕时，整个工程也就完成了。每个项目都需要一定的工作时间。工程最后总耗时是从第一个项目开始到最后一个项目结束的这段时间。各个项目之间可能存在也可以不存在相互制约关系。如果有制约关系，则可能是以下四种之一（设两个项目分别为p和q)：（1）SAS p q(p Sart After q Start，项目p在项目q开始之后才能开始）（2）F

26、AS p q(p Finish After q Start，项目p在项目q开始之后才能结束）（3）SAF p q(p Sart After q Start，项目p在项目q结束之后才能开始）（4）FAF p q(p Finish After q Start，项目p在项目q结束之后才能结束）如果没有制约关系，则可同时进行。例如：SAF 1 3表示项目1必须在项目3完成后才能开始。若项目3工作时间为3，起始时刻为2，则项目1最早在时刻5才能开始。作为SERCOI小组的项目负责人，请你根据各个项目的工作时间及先后关系，找出一种安排工程的方案，使整个工程尽可能快的完成。,作业：工程规划(project)

27、,问题描述：,最短路径问题的求解,输入 输入文件的第一行为项目总数N（1N100)，设项目的编号依次为1，2，N。下面N行依次为完成每个项目所需的工作时间（每个项目占一行）。这个时间为不超过100的正整数。接下来若干行是一些项目间先后次序关系的列表，每行的格式为：（(其中：为SAS、FAS、SAF、FAF中的任意一个，“（”表示一个空格符。整个文件以一个字母“”表示结束（单独占一行）输出 若问题有解，则输出文件有N行，依次输出项目1到项目N的最早开始时间（设整个工程从0时刻开始）。每行的格式为：（项目编号 最早开始时间）。若问题无解，则输出文只有一行，为一个正整数0。,最短路径问题的求解,输入输出示例1project.in3234SAF 2 1FAF 3 2project.out1 02 23 1,输入输出示例2project.in3111SAF 2 1SAF 3 2SAF 1 3 project.out0,