最短路径问题的求解.PPT

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、 A

4、CD、 ACE三个新结点，自然由 AD可以展开得到 ADB、 ADC、 ADE，由 AE可以展开得到 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） 三个结点

7、，并把结点 AC标记为已展开；3、 再从未展开的所有结点中找出距离最小的一个展开，即展开 AB（ 7） 结点，得到 ABC（ 12）、 ABD（ 20）、 ABE（ 19） 三个结点，并把结点 AB标记为已展开；4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开 ACB（ 8） 结点， ；5、 每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有 5个字母）时，即得到了结果。 最短路径问题的求解 小结： 由上可见，启发式搜索和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离 A点最近的那个结点（或是估

8、价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。最短路径问题的求解 例 2、题目基本同例 1，现在把权定义成距离，现在要求 A点到 E点的最短路径，但并不要求每个城市都要走一遍。 例 1、假设 A、 B、 C、 D、 E各个城市之间旅费如下图红色数字所示。某人想从城市 A出发游览各城市一遍，而所用旅费最少，试编程输出结果。 问题分析 既然不要求每个点都要走一遍，只要距离最短即可，那么普通的宽度优先搜索已经没有什么意义了，实际上就是穷举。那么等代价搜索能不能再用在这题上呢

9、？答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。是不是搜索到一个结点是以 E结束时就停止呢？显然不对。那么是不是要把所有以 E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。实际上， 应该是搜索到：当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是 E时，这个结点就是我们所要求的答案！因为比这个结点大的点再展开得到的解显然不可能比这个结点优！那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍这种求最短路径问题的其它几种成熟算法。 最短路径问题的求解 四、宽度优先搜索 +剪枝搜索之所以低效，是因为在搜索过程中存在着大

10、量的重复和不必要的搜索。因此，提高搜索效率的关键在于减少无意义的搜索。 假如在搜索时已经搜出从起点 A到点 B的某一条路径的长度是 X， 那么我们就可以知道，从 A到 B的最短路径长度必定 X， 因此，其他从 A到 B的长度大于或等于 X的路径可以一律剔除。 具体实现时，可以开一个数组 h1.n， n是结点总数， hi表示从起点到结点 i的最短路径长度。算法流程如下：1、 初始化：将起点 start入队， hstart:=0， hk:=maxlongint(1Dk+gk,j then begin Dj:= Dk+gk,j; c:=true; end;Until not c；这种算法是产生这样一

11、个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。 最短路径问题的求解 六、动态规划动态规划算法已经成为了许多难题的首选算法。某些最短路径问题也可以用动态规划来解决，通常这类最短路径问题所对应的图必须是有向无回路图。因为如果存在回路，动态规划的无后效性就无法满足。我们知道，动态规划算法与递归算法的不同之处在于它们的算法表达式：递归：类似 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)等值的改变而确定跟谁相关。为了给问题划分阶段，必须对图进行一次拓扑排序，然后按照拓扑排序的结果来动态规划。譬如，有如下两个有向图： 3BD C E A9852143BD C E A985214