d 图2 考虑从点1到点j的路,按中途所经过的线段数目分类,用d表示从点1到点j的且限制中途 经过的线段数目不超过m的这类路中的一条最短路之长,研究dm+,即所经线段数目为(m+1) 时的最短路长,易见它或者等于d,或者等于min{4+d4},于是有 dn += mind, mind +d,)i 而1到n的最短路即为dn-1。 分析计算量:关系式(1)中,m取1,2,…;(n-2),对每一个固定的m,j取2,3,…,n, 对于固定的m和j,一般说来,要经过(n-1)次加法运算和比较运算才能得到dm,因此计算量 是O(n3)。这实际上就是动态规划的顺推算法,按照动态规划的最优化原理:“作为整个过程的最优 策略,具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的 诸决策必须构成最优策略。而对于无向图说来,起点到终点的最短路自然也是终点到起点的最短路”。 当所有线段的长度都是正数,还有更好的算法: Dijkstra算法(标号算法)。它的计算量为O(n2) 具体做法是:先对起点标号,每步考察已标号顶点的相邻顶点,把距起点最近的顶点标号,直到终 点被标号,按标号反向追踪即得到最短路。 例:求下图中A到B的最短路。 标号过程如下:7 1 2 4 3 j n d12 d13 图 2 考虑从点 1 到点 j 的路，按中途所经过的线段数目分类，用 m j d 表示从点 1 到点 j 的且限制中途 经过的线段数目不超过 m 的这类路中的一条最短路之长，研究 m 1 d j + ，即所经线段数目为（m＋1） 时的最短路长，易见它或者等于 m j d ，或者等于 min{ } m k kj k j d d  + ，于是有 1 min{ ,min{ }} m m m j j k kj k j d d d d +  = + （1） 而 1 到 n 的最短路即为 n 1 dn − 。 分析计算量：关系式（1）中，m 取 1，2，···，（n－2），对每一个固定的 m，j 取 2，3，···，n， 对于固定的 m 和 j，一般说来，要经过（n－1）次加法运算和比较运算才能得到 m 1 d j + ，因此计算量 是 3 O n( ) 。这实际上就是动态规划的顺推算法，按照动态规划的最优化原理：“作为整个过程的最优 策略，具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的 诸决策必须构成最优策略。而对于无向图说来，起点到终点的最短路自然也是终点到起点的最短路”。 当所有线段的长度都是正数，还有更好的算法：Dijkstra 算法（标号算法）。它的计算量为 2 O n( ) 。 具体做法是：先对起点标号，每步考察已标号顶点的相邻顶点，把距起点最近的顶点标号，直到终 点被标号，按标号反向追踪即得到最短路。 例：求下图中 A 到 B 的最短路。 1 6 5 3 2 A 4 1 3 1 1 2 2 2 1 5 3 2 B 标号过程如下：