最短路径问题的求解.ppt

《最短路径问题的求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、　　实际上我们知道，递归（深搜）之类的算法一般用于求所有解问题（例如求从A出发每个城市都要走一遍一共有哪几种走法？），所以这些算法对于求最短路径这类最优解问题显然是不合适的。首先，对于这类图，我们都应该先建立一个邻接矩阵，存放任意两点间的数据（如距离、费用、时间等），以便在程序中方便调用，以下介绍几种常见的、更好的求最短路径问题的算法。最短路径问题的求解一、宽度优先搜索　　宽搜也并不是解决这类问题的优秀算法，这里只是简单介绍一下算法思路，为后面的优秀算法做个铺垫。具体如下：　　1、从A点开始依次展开得到AB

4、、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其旅费；　　2、再次由AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然由AD可以展开得到ADB、ADC、ADE，由AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其旅费；　　3、再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED、……、AEDB、AEDC，每个结点也需记录下其旅费；　　4、再把第

5、四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其旅费；　　5、到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目的解了。　　由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少的那条，显而易见也是一种很费时的算法。最短路径问题的求解二、启发式搜索　　在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的

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

7、，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是：　　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

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