《最短路径问题的求解.ppt》由会员分享，可在线阅读，更多相关《最短路径问题的求解.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最短路径问题的求解最短路径问题的求解 最短路径是图论中的一个重要问题，具有很高的实用价值，也是信息最短路径是图论中的一个重要问题，具有很高的实用价值，也是信息学竞赛中常见的一类中等难度的题目，这类问题很能联系实际，考察学生学竞赛中常见的一类中等难度的题目，这类问题很能联系实际，考察学生的建模能力，反映出学生的创造性思维，因为有些看似跟最短路径毫无关的建模能力，反映出学生的创造性思维，因为有些看似跟最短路径毫无关系的问题，也可以归结为最短路径问题来求解。系的问题，也可以归结为最短路径问题来求解。在带权图在带权图G=G=（V V，E E）中，若顶点）中，若顶点 Vi,Vj Vi,Vj是图是图G G
2、的两个顶点，从顶点的两个顶点，从顶点ViVi到到VjVj的路径长度定义为路径上各条边的权值之和。从顶点的路径长度定义为路径上各条边的权值之和。从顶点ViVi到到VjVj可能有多条可能有多条路径，其中路径长度最小的一条路径称为顶点路径，其中路径长度最小的一条路径称为顶点ViVi到到VjVj的最短路径。的最短路径。一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。对于不带权的图，只要人为的把每条边加上权值对于不带权
3、的图，只要人为的把每条边加上权值1 1，即可当作带权图，即可当作带权图一样处理了。一样处理了。最短路径问题的求解最短路径问题的求解 例例1 1、假设、假设A A、B B、C C、D D、E E各个城市之间旅费如下图红各个城市之间旅费如下图红色数字所示。某人想从城市色数字所示。某人想从城市A A出发出发游览各城市一遍游览各城市一遍，而，而所用所用旅费最少旅费最少，试编程输出结果。，试编程输出结果。问题分析问题分析 解这类问题时，很多同学往往不得要领，采用穷解这类问题时，很多同学往往不得要领，采用穷举法把所有可能的情况全部列出，再找出其中旅费最举法把所有可能的情况全部列出，再找出其中旅费最少的那条
4、路径；或者采用递归（深搜）找出所有路径，少的那条路径；或者采用递归（深搜）找出所有路径，再找出旅费最少的那条。但这两种方法都是费时非常再找出旅费最少的那条。但这两种方法都是费时非常多的解法，如果城市数目多的话则很可能要超时了。多的解法，如果城市数目多的话则很可能要超时了。实际上我们知道，递归（深搜）之类的算法一般实际上我们知道，递归（深搜）之类的算法一般用于求所有解问题（例如求从用于求所有解问题（例如求从A A出发每个城市都要走一出发每个城市都要走一遍一共有哪几种走法？），所以这些算法对于求最短遍一共有哪几种走法？），所以这些算法对于求最短路径这类最优解问题显然是不合适的。路径这类最优解问题显
5、然是不合适的。首先，对于这类图，我们都应该先建立一个邻接矩阵，存放首先，对于这类图，我们都应该先建立一个邻接矩阵，存放任意两点间的数据（如距离、费用、时间等），以便在程序中方任意两点间的数据（如距离、费用、时间等），以便在程序中方便调用，以下介绍几种常见的、更好的求最短路径问题的算法。便调用，以下介绍几种常见的、更好的求最短路径问题的算法。最短路径问题的求解最短路径问题的求解 一、一、宽度优先搜索宽度优先搜索宽搜也并不是解决这类问题的优秀算法，这里只是简单介绍一下算法思路，为后宽搜也并不是解决这类问题的优秀算法，这里只是简单介绍一下算法思路，为后面的优秀算法做个铺垫。具体如下：面的优秀算法做个
6、铺垫。具体如下：1 1、从从A A点开始依次展开得到点开始依次展开得到ABAB、ACAC、ADAD、AEAE四个新结点（第二层结点），当然四个新结点（第二层结点），当然每个新结点要记录下其旅费；每个新结点要记录下其旅费；2 2、再次由再次由ABAB展开得到展开得到ABCABC、ABDABD、ABEABE三个新结点（第三层结点），而由三个新结点（第三层结点），而由ACAC结点结点可展开得到可展开得到ACBACB、ACDACD、ACEACE三个新结点，自然由三个新结点，自然由ADAD可以展开得到可以展开得到ADBADB、ADCADC、ADEADE，由，由AEAE可以展开得到可以展开得到AEBAEB
7、、AECAEC、AEDAED等新结点，对于每个结点也须记录下其旅费；等新结点，对于每个结点也须记录下其旅费；3 3、再把第三层结点全部展开，得到所有的第四层结点：再把第三层结点全部展开，得到所有的第四层结点：ABCDABCD、ABCEABCE、ABDCABDC、ABDEABDE、ABECABEC、ABEDABED、AEDBAEDB、AEDCAEDC，每个结点也需记录下其旅费；，每个结点也需记录下其旅费；4 4、再把第四层结点全部展开，得到所有的第五层结点：再把第四层结点全部展开，得到所有的第五层结点：ABCDEABCDE、ABCEDABCED、AEDBCAEDBC、AEDCBAEDCB，每个结
8、点也需记录下其旅费；，每个结点也需记录下其旅费；5 5、到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目的解了。的解了。由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少的那由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少的那条，显而易见也是一种很费时的算法。条，显而易见也是一种很费时的算法。最短路径问题的求解最短路径问题的求解 二、二、启发式搜索启发式搜索在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开
9、，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能越快找到答案。这种算法实现起来并不难，只不过难在找准估价函数，大越快找到答案。这种算法实现
10、起来并不难，只不过难在找准估价函数，大家可以自已找相关资料学习和思考。家可以自已找相关资料学习和思考。最短路径问题的求解最短路径问题的求解 三、等代价搜索法三、等代价搜索法等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到处在于：它不需要去另找专门的估价函数，而是以该结点到A A点的距离作为估价值，点的距离作为估价值
11、，也就是说，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是：也就是说，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是：1 1、从从A A点开始依次展开得到点开始依次展开得到ABAB（7 7）、）、ACAC（3 3）、）、ADAD（1010）、）、AEAE（1515）四个新结）四个新结点，把第一层结点点，把第一层结点A A标记为已展开，并且每个新结点要记录下其旅费（括号中的数字）标记为已展开，并且每个新结点要记录下其旅费（括号中的数字）；2 2、把未展开过的把未展开过的ABAB、ACAC、ADAD、AEAE四个结点中距离最小的一个展开，即展开四个结点中距离最小的一个展开，即展开A
12、CAC（3 3）结点，得到）结点，得到ACBACB（8 8）、）、ACDACD（1616）、）、ACEACE（1313）三个结点，并把结点）三个结点，并把结点ACAC标记为标记为已展开；已展开；3 3、再从未展开的所有结点中找出距离最小的一个展开，即展开再从未展开的所有结点中找出距离最小的一个展开，即展开ABAB（7 7）结点，）结点，得到得到ABCABC（1212）、）、ABDABD（2020）、）、ABEABE（1919）三个结点，并把结点）三个结点，并把结点ABAB标记为已展开；标记为已展开；4 4、再次从未展开的所有结点中找出距离最小的一个展开，即展开再次从未展开的所有结点中找出距离最
13、小的一个展开，即展开ACBACB（8 8）结）结点，点，；5 5、每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有出现目标情况（结点含有5 5个字母）时，即得到了结果。个字母）时，即得到了结果。最短路径问题的求解最短路径问题的求解 小结：小结：由由上上可可见见，启启发发式式搜搜索索和和等等代代价价搜搜索索法法并并没没有有象象宽宽度度优优先先搜搜索索一一样样展展开开所所有有结结点点，只只是是根根据据某某一一原原则则（或或某某一一估估价价函函数数值值）每每次次展展开开距距离离A A点点最最近近的的
14、那那个个结结点点（或或是是估估价价函函数数计计算算出出的的最最可可能能的的那那个个结结点点），反反复复下下去去即即可可最最终终得得到到答答案案。虽虽然然中中途途有有时时也也展展开开了了一一些些并并不不是是答答案案的的结结点点，但但这这种种展展开开并并不不是是大大规规模模的的，不不是是全全部部展展开开，因而耗时要比宽度优先搜索小得多。因而耗时要比宽度优先搜索小得多。最短路径问题的求解最短路径问题的求解 例例2 2、题目基本同例、题目基本同例1 1，现在把权定义成距离，现在，现在把权定义成距离，现在要求要求A A点到点到E E点的最短路径，但并不要求每个城市都点的最短路径，但并不要求每个城市都要走
15、一遍。要走一遍。例例1 1、假设、假设A A、B B、C C、D D、E E各个城市之间旅费如下图红各个城市之间旅费如下图红色数字所示。某人想从城市色数字所示。某人想从城市A A出发游览各城市一遍，而出发游览各城市一遍，而所用旅费最少，试编程输出结果。所用旅费最少，试编程输出结果。问题分析问题分析 既然不要求每个点都要走一遍，只要距离最短即可，那么普通的宽度优先搜索已经没有什么意义了，既然不要求每个点都要走一遍，只要距离最短即可，那么普通的宽度优先搜索已经没有什么意义了，实际上就是穷举。那么等代价搜索能不能再用在这题上呢？答案是肯定的，但到底搜索到什么时候才能得实际上就是穷举。那么等代价搜索能
16、不能再用在这题上呢？答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。到答案呢？这可是个很荆手的问题。是不是搜索到一个结点是以是不是搜索到一个结点是以E E结束时就停止呢？显然不对。结束时就停止呢？显然不对。那么是不是要把所有以那么是不是要把所有以E E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。实际上，实际上，应该是搜索到：当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）应该是搜索到：当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是
17、的最后一个字母是E E时，这个结点就是我们所要求的答案！因为比这个结点大的点再展开得到的解显然不可时，这个结点就是我们所要求的答案！因为比这个结点大的点再展开得到的解显然不可能比这个结点优！能比这个结点优！那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍这种求最短路径问题的其它几种成熟算那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍这种求最短路径问题的其它几种成熟算法。法。最短路径问题的求解最短路径问题的求解 四、宽度优先搜索四、宽度优先搜索+剪枝剪枝 搜搜索索之之所所以以低低效效，是是因因为为在在搜搜索索过过程程中中存存在在着着大大量量的的重重复复和和不不必必要要的的搜搜索索。
18、因因此此，提提高高搜搜索索效效率率的的关关键键在在于于减减少少无无意意义义的的搜搜索索。假假如如在在搜搜索索时时已已经经搜搜出出从从起起点点A A到到点点B B的的某某一一条条路路径径的的长长度度是是X X，那那么么我我们们就就可可以以知知道道，从从A A到到B B的的最最短短路路径径长长度度必必定定XX，因因此此，其其他他从从A A到到B B的的长长度度大大于于或或等等于于X X的的路路径径可可以以一一律律剔剔除除。具具体体实现时，可以开一个数组实现时，可以开一个数组h1.nh1.n，n n是结点总数，是结点总数，hihi表示从起点到结点表示从起点到结点i i的最短路径长度。的最短路径长度。
19、算法流程如下：算法流程如下：1 1、初始化：初始化：将起点将起点startstart入队，入队，hstart:=0hstart:=0，hk:=maxlongint(1=k=nhk:=maxlongint(1=k=n，且，且kstart)kstart)。2 2、repeatrepeat 取出队头结点赋给取出队头结点赋给t t；while t while t有相邻的结点没被扩展有相邻的结点没被扩展 begin begin t t扩展出新的结点扩展出新的结点newpnewp；如果如果 ht+wt,newp hnewp ht+wt,newp hnewp，则将则将newpnewp入队，把入队，把hnew
20、phnewp的值更新为的值更新为ht+wt,newpht+wt,newp；End End until until 队列空；队列空；最短路径问题的求解最短路径问题的求解 五、迭代法五、迭代法 该算法的中心思想是：任意两点该算法的中心思想是：任意两点i,ji,j间的最短距离（记为间的最短距离（记为DijDij）会等于从）会等于从i i点出发到达点出发到达j j点的以任一点为点的以任一点为中转点的所有可能的方案中，距离最短的一个。即：中转点的所有可能的方案中，距离最短的一个。即：Dij=min Dij,Dik+Dkj Dij=min Dij,Dik+Dkj，1=k=n1=k=n。这样，我们就找到了一
21、个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是这样，我们就找到了一个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到数据不再变化为止，这时即可得到A A到到E E的最短路径。的最短路径。算法流程如下：算法流程如下：Di Di表示从起点到表示从起点到i i的最短路的长度，的最短路的长度，g g是邻接矩阵，是邻接矩阵，s s表示起点；表示起点；1
22、1、Di:=gs,i(1=i=n)Di:=gs,i(1=iDk+gk,j then if DjDk+gk,j then begin Dj:=Dk+gk,j;c:=true;end;begin Dj:=Dk+gk,j;c:=true;end;Until not c Until not c；这种算法是产生这样一个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有这种算法是产生这样一个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值
23、就是对应的两点间的最短距离。的两点间的最短距离。最短路径问题的求解最短路径问题的求解 六、动态规划六、动态规划 动动态态规规划划算算法法已已经经成成为为了了许许多多难难题题的的首首选选算算法法。某某些些最最短短路路径径问问题题也也可可以以用用动动态态规规划划来来解解决决，通通常常这这类类最最短短路路径径问问题题所所对对应应的的图图必必须须是是有有向向无无回回路路图图。因因为为如如果果存存在在回回路路，动动态态规规划划的的无无后后效效性性就就无无法法满满足。足。我们知道，动态规划算法与递归算法的不同之处在于它们的算法表达式：我们知道，动态规划算法与递归算法的不同之处在于它们的算法表达式：递归：类
24、似递归：类似f(n)=x1*f(n-1)+x2*f(n-2)f(n)=x1*f(n-1)+x2*f(n-2)，即可以找到一个确定的关系的表达式；，即可以找到一个确定的关系的表达式；动态规划：类似动态规划：类似f(n)=min(f(n-1)+x1,f(n-2)+x2)f(n)=min(f(n-1)+x1,f(n-2)+x2)，即我们无法找到确定关系的表达式，只能，即我们无法找到确定关系的表达式，只能找到这样一个不确定关系的表达式，找到这样一个不确定关系的表达式，f(n)f(n)的值是动态的，随着的值是动态的，随着f(n-1),f(n-2)f(n-1),f(n-2)等值的改变而确定跟谁相等值的改变
25、而确定跟谁相关。关。为了给问题划分阶段，必须对图进行一次拓扑排序，然后按照拓扑排序的结果来动态规划。为了给问题划分阶段，必须对图进行一次拓扑排序，然后按照拓扑排序的结果来动态规划。譬如，有如下两个有向图：譬如，有如下两个有向图：3BD C E A9852143BD C E A985214最短路径问题的求解最短路径问题的求解 右图因为存在回路而不能用动态规划。而左图是无回路的，所以可以用动态规划解决。右图因为存在回路而不能用动态规划。而左图是无回路的，所以可以用动态规划解决。对左图拓扑排序，得到的序列是对左图拓扑排序，得到的序列是A A、B B、D D、C C、E E。设设F(E)F(E)表示从
26、表示从A A到到E E的最短路径长度，然后按照拓扑序列的先后顺序进行动态规划：的最短路径长度，然后按照拓扑序列的先后顺序进行动态规划：F(A)=0 F(A)=0 F(B)=min F(A)+3=3 F(B)=min F(A)+3=3 F(D)=min F(A)+8,F(B)+2=5 F(D)=min F(A)+8,F(B)+2=5 F(C)=min F(B)+9,F(D)+5=10 F(C)=min F(B)+9,F(D)+5=10 F(E)=min F(D)+1,F(C)+4=6 F(E)=min F(D)+1,F(C)+4=6总的式子是：总的式子是：F(i)=min F(k)+dis(i,
27、k)F(i)=min F(k)+dis(i,k)，k k与与i i必须相连，且在拓扑序列中，必须相连，且在拓扑序列中，k k在在i i之前。之前。3BD C E A9852143BD C E A985214最短路径问题的求解最短路径问题的求解 七、标号法七、标号法标号法是一种非常直观的求最短路径的算法，单从分析过程来看，我们可以用一个数轴简单地表示标号法是一种非常直观的求最短路径的算法，单从分析过程来看，我们可以用一个数轴简单地表示这种算法：这种算法：1 1、以以A A点为点为0 0点，展开与其相邻的点，并在数轴中标出。点，展开与其相邻的点，并在数轴中标出。2 2、因为、因为C C点离起点点离
28、起点A A最近，因此可以断定最近，因此可以断定C C点一定是由点一定是由A A直接到直接到C C点这条路径是最短的（因为点这条路径是最短的（因为A A、C C两点两点间没有其它的点，所以间没有其它的点，所以C C点可以确定是由点可以确定是由A A点直接到达为最短路径）。因而就可以以已经确定的点直接到达为最短路径）。因而就可以以已经确定的C C点为点为当前展开点，展开与当前展开点，展开与C C点想连的所有点点想连的所有点AA、BB、DD、EE。3 3、由数轴可见，、由数轴可见，A A与与AA点相比，点相比，A A点离原点近，因而保留点离原点近，因而保留A A点，删除点，删除AA点，相应的，点，相
29、应的，B B、BB点保留点保留B B点，点，D D、DD保留保留DD，E E、EE保留保留EE，得到下图：，得到下图：最短路径问题的求解最短路径问题的求解 4 4、此时再以离原点最近的未展开的点、此时再以离原点最近的未展开的点B B联接的所有点，处理后，再展开离原点最近未展开的联接的所有点，处理后，再展开离原点最近未展开的D D点，点，处理后得到如下图的最终结果：处理后得到如下图的最终结果：5 5、由上图可以得出结论：点、由上图可以得出结论：点C C、B B、D D、E E就是点就是点A A到它们的最短路径（注意：这些路径并不是经过了到它们的最短路径（注意：这些路径并不是经过了所有点，而是只经
30、过了其中的若干个点，而且到每一个点的那条路径不一定相同）。因而所有点，而是只经过了其中的若干个点，而且到每一个点的那条路径不一定相同）。因而A A到到E E的最的最短距离就是短距离就是1313。至于它经过了哪几个点大家可在上述过程中加以记录即可。至于它经过了哪几个点大家可在上述过程中加以记录即可。最短路径问题的求解最短路径问题的求解 八、八、DijkstraDijkstra算法（从一个顶点到其余各顶点的最短路径，单源最短路径）算法（从一个顶点到其余各顶点的最短路径，单源最短路径）例例3 3、如下图，假设、如下图，假设C C1 1,C,C2 2,C,C3 3,C,C4 4,C,C5 5,C,C6
31、 6是六座城市，他们之间的连线表示两是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C C1 1到到C Ci i的最短路径的最短路径(2i6)(2i6)，输出路径序列及最短路径的路程长度。，输出路径序列及最短路径的路程长度。最短路径问题的求解最短路径问题的求解 问题分析问题分析 对对于于一一个个含含有有n n个个顶顶点点和和e e条条边边的的图图来来说说，从从某某一一个个顶顶点点ViVi到到其其余余任任一一顶顶点点VjVj的的最最短短路路径径，可可能能是是它它们们之之间间的的边边（ViVi，Vj
32、Vj），也也可可能能是是经经过过k k个个中中间间顶顶点点和和k+1k+1条条边边所所形形成成的的路路径径(1kn-2)(1kn-2)。下面给出解决这个问题的下面给出解决这个问题的DijkstraDijkstra算法思想。算法思想。设图设图G G用邻接矩阵的方式存储在用邻接矩阵的方式存储在GAGA中，中，GAi,j=maxintGAi,j=maxint表示表示ViVi，VjVj是不关联的，否则为权值是不关联的，否则为权值（大于（大于0 0的实数）。设集合的实数）。设集合S S用来保存已求得最短路径的终点序号，初始时用来保存已求得最短路径的终点序号，初始时S=ViS=Vi表示只有源点，表示只有源
33、点，以后每求出一个终点以后每求出一个终点VjVj，就把它加入到集合中并作为新考虑的中间顶点。设数组，就把它加入到集合中并作为新考虑的中间顶点。设数组dist1.ndist1.n用来用来存储当前求得的最短路径，初始时存储当前求得的最短路径，初始时ViVi，VjVj如果是关联的，则如果是关联的，则distjdistj等于权值，否则等于等于权值，否则等于maxintmaxint，以后随着新考虑的中间顶点越来越多，以后随着新考虑的中间顶点越来越多，distjdistj可能越来越小。再设一个与可能越来越小。再设一个与distdist对应的数组对应的数组path1.npath1.n用来存放当前最短路径的边
34、，初始时为用来存放当前最短路径的边，初始时为ViVi到到VjVj的边，如果不存在边则为空。的边，如果不存在边则为空。执行时，先从执行时，先从S S以外的顶点（即待求出最短路径的终点）所对应的以外的顶点（即待求出最短路径的终点）所对应的distdist数组元素中，找出其数组元素中，找出其值最小的元素（假设为值最小的元素（假设为distmdistm），该元素值就是从源点），该元素值就是从源点ViVi到终点到终点VmVm的最短路径长度，对应的的最短路径长度，对应的pathmpathm中的顶点或边的序列即为最短路径。接着把中的顶点或边的序列即为最短路径。接着把VmVm并入集合并入集合S S中，然后以中
35、，然后以VmVm作为新考虑的中间作为新考虑的中间顶点，对顶点，对S S以外的每个顶点以外的每个顶点VjVj，比较，比较distm+GAm,jdistm+GAm,j的的distjdistj的大小，若前者小，表明加入了的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替distjdistj，同时把，同时把VjVj或或边（边（VmVm，VjVj）并入到）并入到pathjpathj中。重复以上过程中。重复以上过程n-2n-2次，即可在次，即可在distdist数组中得到从源点到其余各终数组中得到从源
36、点到其余各终点的最段路径长度，对应的点的最段路径长度，对应的pathpath数组中保存着相应的最段路径。数组中保存着相应的最段路径。对于上图，采用对于上图，采用DijkstraDijkstra算法找出算法找出C C1 1到到C Ci i之间的最短路径之间的最短路径(2i6)(2i6)的过程如下：的过程如下：最短路径问题的求解最短路径问题的求解 123456Dist048maxintmaxintmaxintPathC1C1,C2C1,C3初始时：初始时：第一次：选择第一次：选择m=2m=2，则，则S=CS=C1 1,C,C2 2，计算比较，计算比较dist2+GA2,jdist2+GA2,j与与
37、distjdistj的大小的大小 123456Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：选择第二次：选择m=3m=3，则，则S=CS=C1 1,C,C2 2,C,C3 3，计算比较，计算比较dist3+GA3,jdist3+GA3,j与与distjdistj的大小的大小 123456Dist04789maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5第三次：选择第三次：选择m=4m=4，S=CS=C1 1,C,C2 2,C,C3 3,C,C4 4，计算比较，计算比较dist4+GA4,jd
38、ist4+GA4,j与与distjdistj的大小的大小 123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6最短路径问题的求解最短路径问题的求解 第四次：选择第四次：选择m=5m=5，则，则S=CS=C1 1,C,C2 2,C,C3 3,C,C4 4,C,C5 5，计算比较，计算比较dist5+GA5,jdist5+GA5,j与与distjdistj的大小的大小 123456Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因为该图的度因
39、为该图的度n=6n=6，所以执行，所以执行n-2=4n-2=4次后结束，此时通过次后结束，此时通过distdist和和pathpath数组可以看出：数组可以看出：C C1 1到到C C2 2的最短路径为：的最短路径为：C C1 1CC2 2，长度为：，长度为：4 4；C C1 1到到C C3 3的最短路径为：的最短路径为：C C1 1CC2 2CC3 3，长度为：，长度为：7 7；C C1 1到到C C4 4的最短路径为：的最短路径为：C C1 1CC2 2CC4 4，长度为：，长度为：8 8；C C1 1到到C C5 5的最短路径为：的最短路径为：C C1 1CC2 2CC3 3CC5 5，
40、长度为：，长度为：9 9；C C1 1到到C C6 6的最短路径为：的最短路径为：C C1 1CC2 2CC3 3CC5 5CC6 6，长度为：，长度为：1313；123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6最短路径问题的求解最短路径问题的求解 下下面面给给出出具具体体的的DijkstraDijkstra算算法法框框架架（注注：为为了了实实现现上上的的方方便便，我我们们用用一一个个一一维维数数组组s1.ns1.n代代替替集集合合S S，用用来来保保存存已已求求得得最最短短路路径径的的终终点点集集合合，即即如
41、如果果sj=0sj=0表表示示顶顶点点VjVj不不在在集集合合中中，反反之之，sj=1sj=1表表示示顶顶点点VjVj已在集合中）。已在集合中）。Procedure Dijkstra(GA,dist,path,i)Procedure Dijkstra(GA,dist,path,i)；表示求表示求ViVi到图到图G G中其余顶点的最短路径，中其余顶点的最短路径，GAGA为图为图G G的邻接矩阵，的邻接矩阵，distdist和和pathpath为变量型参数，为变量型参数，其中其中pathpath的基类型为集合的基类型为集合 Begin Begin For j:=1 To n Do Begin Fo
42、r j:=1 To n Do Begin 初始化初始化 If ji Then sj:=0 Else sj:=1 If ji Then sj:=0 Else sj:=1；distj:=GAi,j distj:=GAi,j；If distjmaxint Then pathj:=i+j Else pathj:=If distjmaxint Then pathj:=i+j Else pathj:=；End End；最短路径问题的求解最短路径问题的求解 For k:=1 To n-2 DoFor k:=1 To n-2 Do Begin Begin w:=maxint w:=maxint；m:=im:=
43、i；For j:=1 To n Do For j:=1 To n Do 求出第求出第k k个终点个终点VmVm If(sj=0)and(distjw)Then Begin m:=j If(sj=0)and(distjw)Then Begin m:=j；w:=distjw:=distj；End End；If mi Then sm:=1 else exit If mi Then sm:=1 else exit；若条件成立，则把若条件成立，则把VmVm加入到加入到S S中，中，否则退出循环，因为剩余的终点，其最短路径长度均为否则退出循环，因为剩余的终点，其最短路径长度均为maxintmaxint，无
44、需再计算下去，无需再计算下去 For j:=1 To n Do For j:=1 To n Do 对对sj=0sj=0的更优元素作必要修改的更优元素作必要修改 If(sj=0)and(distm+GAm,jdistj)If(sj=0)and(distm+GAm,jdistj)Then Begin Distj:=distm+GAm,j Then Begin Distj:=distm+GAm,j；pathj:=pathm+jpathj:=pathm+j；EndEnd；End End；EndEnd；最短路径问题的求解最短路径问题的求解 九、九、FloydFloyd算法算法例例4 4、求任意一对顶点之
45、间的最短路径。、求任意一对顶点之间的最短路径。问题分析问题分析 这个问题的解法有两种：一是分别以图中的每个顶点为源点共这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用调用n n次次DijkstraDijkstra算法算法，这种算法的时间复杂度为，这种算法的时间复杂度为O O（n n3 3）；另外还有一种算法：）；另外还有一种算法：FloydFloyd算法算法，它的思路，它的思路简单，但时间复杂度仍然为简单，但时间复杂度仍然为O O（n n3 3），下面介绍），下面介绍FloydFloyd算法。算法。设具有设具有n n个顶点的一个带权图个顶点的一个带权图G G的邻接矩阵用的邻接矩阵用G
46、AGA表示，再设一个与表示，再设一个与GAGA同类型的表示同类型的表示每对顶点之间最短路径长度的二维数组每对顶点之间最短路径长度的二维数组A A，A A的初值等于的初值等于GAGA。FloydFloyd算法需要在算法需要在A A上进行上进行n n次运算，每次以次运算，每次以V Vk k（1kn1kn）作为新考虑的中间点，求出每对顶点之间的当前最短）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，路径长度，最后依次运算后，A A中的每个元素中的每个元素AiAi，jj就是图就是图G G中从顶点中从顶点V Vi i到顶点到顶点V Vj j的最的最短路径长度。再设一个二维数组短
47、路径长度。再设一个二维数组P1.n,1.nP1.n,1.n，记录最短路径，其元素类型为集合类，记录最短路径，其元素类型为集合类型型set of 1.nset of 1.n。Floyd Floyd算法的具体描述如下：算法的具体描述如下：最短路径问题的求解最短路径问题的求解 Procedure Floyd(GAProcedure Floyd(GA，A A，P)P)；Begin Begin For i:=1 To n Do For i:=1 To n Do 最短路径长度数组和最短路径数组初始化最短路径长度数组和最短路径数组初始化 For j:=1 To n Do For j:=1 To n Do B
48、egin Begin Ai,j:=GAi,j Ai,j:=GAi,j；If Ai,jmaxint Then pi,j:=i+j If Ai,jmaxint Then pi,j:=i+jElse pi,j:=Else pi,j:=；End End；For k:=1 To n Do n For k:=1 To n Do n次运算次运算 For i:=1 To n Do For i:=1 To n Do For j:=1 To n Do For j:=1 To n Do Begin Begin If(i=k)or(j=k)or(i=j)Then Continue If(i=k)or(j=k)or(i
49、=j)Then Continue；无需计算，直接进入下一轮循环无需计算，直接进入下一轮循环 If Ai,k+Ak,jAi,j Then Begin If Ai,k+Ak,jAi,j Then Begin 找到更短路径、保存找到更短路径、保存 Ai,j Ai,j：=Ai,k+Ak,j=Ai,k+Ak,j；Pi,j Pi,j：=Pi,k+Pk,j=Pi,k+Pk,j；End End；End End；End End；最短路径问题的求解最短路径问题的求解 总结与思考：总结与思考：最短路径问题的求解还不止这几种算法，比如还有分枝定界等等，而最短路径问题的求解还不止这几种算法，比如还有分枝定界等等，而且大
50、家也可以创造出各种各样的新算法来。不同的最短路径问题到底用哪且大家也可以创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需要对该种算法作什么改动，是非常重要的，这种能力往种算法，以及还需要对该种算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平常的训练中多做这类题目，还要往是很多同学所欠缺的，这需要大家在平常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。多总结，以达到熟能生巧的境界。在学习完最短路径后，有没有人想到：能不能修改这些算法，实现求在学习完最短路径后，有没有人想到：能不能修改这些算法，实现求最长路径的问题呢？最长路径的问题呢？这种