第六章动态规划方法 S1动态规划算法的基本思想 动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在 实际生活中,有一类问题的活动过程可以分成若干个阶段,而且在任 阶段后的行为依赖于该阶段的状态,而与该阶段之前的过程如何达 到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在 50年代,贝尔曼( Richard bellman)等人提出了解决这类问题的“最 优化原理”,从而创建了最优化问题的一种新的算法设计方法一动态 规划。 最优化原理:多阶段过程的最优决策序列应当具有性质:无论过程的 初始状态和初始决策是什么,其余的决策都必须相对于初始决策 所产生的状态构成一个最优决策序列。 对于一个多阶段过程问题,上述最优决策是否存在依赖于该问题是否 有最优子结构性质:原问题的最优解包含了其子问题的最优解。而能 否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。后 面将会看到问题的子结构性质和子问题重叠性质是采用动态规划算 法的两个基本要素。先看两个例子 例1.多段图问题 设G=(VE)是一个赋权有向图,其顶点集V被划分成k>2个不相 交的子集V:1≤≤k,其中,V1和Ⅴ分别只有一个顶点s(称为源)和 个顶点t(称为汇),图中所有的边(uv)的始点和终点都在相邻的两个子
第六章 动态规划方法 §1 动态规划算法的基本思想 动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在 实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任 一阶段后的行为依赖于该阶段的状态，而与该阶段之前的过程如何达 到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在 50 年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最 优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态 规划。 最优化原理：多阶段过程的最优决策序列应当具有性质：无论过程的 初始状态和初始决策是什么，其余的决策都必须相对于初始决策 所产生的状态构成一个最优决策序列。 对于一个多阶段过程问题，上述最优决策是否存在依赖于该问题是否 有最优子结构性质：原问题的最优解包含了其子问题的最优解。而能 否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。后 面将会看到问题的子结构性质和子问题重叠性质是采用动态规划算 法的两个基本要素。先看两个例子： 例1． 多段图问题 设 G=(V,E)是一个赋权有向图，其顶点集 V 被划分成 k>2 个不相 交的子集 Vi: 1≤i≤k，其中，V1和 Vk分别只有一个顶点 s(称为源)和一 个顶点 t(称为汇)，图中所有的边(u,v)的始点和终点都在相邻的两个子
集V和V计+中:u∈V,v∈V+1。 一个5阶段的网络图 多阶段图问题:求由s到t的最小成本路径。 对于每一条由s到t的路径,可以把它看成在k-2个阶段作出的某个 决策序列的相应结果:第i步决策就是确定V*1中那个顶点在这条路 径上。今假设s,v2,V3,,vk-t,t是一条由s到t的最短路径,再假定 从源点s(初始状态)开始,已经作出了到顶点v2的决策(初始决策),则 2就是初始决策产生的状态。若将v2看成是原问题的子问题的初始 状态,解这个子问题就是找一条由v2到t的最短路径。事实上,这条 最短路径一定是v2,V3,…,Vkl,to不然,设v2,q3,…,qk-,t是一条由 v2到t的比v2,v3,…,vk-1,t更短的路径,则s,v2,q3,…,qk,t是一条 由s到t的比s,V2,V,…,vk-l,t更短的路径。与前面的假设矛盾。这 说明多段图问题具有最优子结构性质。 例2.经典0/1背包问题 有n件物品,第i件重量和价值分别是w和pi=1,2,…,n。要 将这n件物品的一部分装入容量为c的背包中,要求每件物品或整个
集 Vi和 Vi＋1中：u∈Vi，v∈Vi＋1。 V1 V2 V3 V4 V5 4 6 9 4 4 2 5 7 2 S 7 3 2 t 3 1 11 5 2 5 11 6 8 一个 5 阶段的网络图 多阶段图问题：求由 s 到 t 的最小成本路径。 对于每一条由 s 到 t 的路径，可以把它看成在 k-2 个阶段作出的某个 决策序列的相应结果：第 i 步决策就是确定 Vi+1中那个顶点在这条路 径上。今假设 s, v2, v3, … , vk-1, t 是一条由 s 到 t 的最短路径，再假定 从源点 s(初始状态)开始，已经作出了到顶点 v2 的决策(初始决策),则 v2 就是初始决策产生的状态。若将 v2 看成是原问题的子问题的初始 状态，解这个子问题就是找一条由 v2到 t 的最短路径。事实上，这条 最短路径一定是 v2, v3, … , vk-1, t。不然，设 v2, q3, … , qk-1, t 是一条由 v2到 t 的比 v2, v3, … , vk-1, t 更短的路径，则 s, v2, q3, … , qk-1, t 是一条 由 s 到 t 的比 s, v2, v3, … , vk-1, t 更短的路径。与前面的假设矛盾。这 说明多段图问题具有最优子结构性质。 例2． 经典 0/1 背包问题 有 n 件物品，第 i 件重量和价值分别是 wi和 pi, i=1, 2, …, n。要 将这 n 件物品的一部分装入容量为 c 的背包中，要求每件物品或整个 1 2 4 6 9 10 11 12 3 7 8 5
装入或不装入,不许分割出一部分装入。0/1背包问题就是要给装包 算法,使得装入背包的物品的总价值最大。这个问题归结为数学规划 问题: max∑Px ∑ 1:X:≤ 0,1},i=1,2,…,n (6.1) 0/1背包问题具有最优子结构性质。事实上,若y,y2…,yn是最优解, 则y2…y将是是0/1背包问题的子问题 max∑P 2≤i≤n st.∑w1x≤c-W,x1∈{0.1},=2,…,n (62 2≤i∑py (6.3) 2≤i≤n 则y1,y2…,y’n将是原问题(61)的可行解,并且使得 Py+∑Py1>∑P1y (64) 这与y,y2,…,yn是最优解相悖。 例3.矩阵连乘问题 给定n个数字矩阵A1,A2,,An,其中A1与A1是可乘的, 1=1,2,,n-1求矩阵连乘A1A2…An的加括号方法,使得所用的数乘次 数最少。 考察两个矩阵相成的情形:C=AB.如果矩阵A,B分别是pXr 和r×q矩阵,则它们的乘积C将是p×q矩阵,其(i,j)元素为 (65 i=1,…p,j=1,,q,因而AB所用的数乘次数是prq。如果有至少3个
装入或不装入，不许分割出一部分装入。0/1 背包问题就是要给装包 算法，使得装入背包的物品的总价值最大。这个问题归结为数学规划 问题： ∑ ≤i≤n i i p x 1 max s.t. w x c x i n i i n i i , {0,1}, 1,2, , 1 ∑ ≤ ∈ = L ≤ ≤ （6.1） 0/1 背包问题具有最优子结构性质。事实上，若 n y , y , , y 1 2 L 是最优解， 则 n y , , y 2 L 将是是 0/1 背包问题的子问题 ∑ ≤i≤n i i p x 2 max s.t. w x c w x i n i i n i i , {0,1}, 2, , 1 2 ∑ ≤ − ∈ = L ≤ ≤ (6.2) 最优解。因为，若 n y' , , y' 2 L 是子问题(6.2)的最优解，且使得 ∑ ≤i≤n i i p y 2 ' > ∑ ≤i≤n i i p y 2 (6.3) 则 n y , y' , , y' 1 2 L 将是原问题(6.1)的可行解，并且使得 ∑ ≤ ≤ + i n i i p y p y 2 1 1 ' > ∑ ≤i≤n i i p y 1 (6.4) 这与 n y , y , , y 1 2 L 是最优解相悖。 例3． 矩阵连乘问题 给定 n 个数字矩阵 A1，A2，…，An，其中 Ai与 Ai+1是可乘的， i=1,2,…,n-1.求矩阵连乘 A1A2⋅⋅⋅An 的加括号方法，使得所用的数乘次 数最少。 考察两个矩阵相成的情形：C=AB.如果矩阵 A，B 分别是 p×r 和 r×q 矩阵，则它们的乘积 C 将是 p×q 矩阵，其(i, j)元素为 ∑ = = r k ij ik kj c a b 1 (6.5) i=1,…,p, j=1,…,q, 因而 AB 所用的数乘次数是 prq。如果有至少 3 个
以上的矩阵连乘则涉及到乘积次序问题,即加括号方法。例如3个 矩阵连乘的加括号方法有两种:(A1A2)A3)和(A1(A2A3)。设A1,A2, A3分别是p×p1,p×p2,p2×p3矩阵,则以上两种乘法次序所用的 数乘次数分别为:popp2+pop2p3和popp3+pp2p3。如果po=10,p1=100, p2=5,p3=50,则两种乘法所用的数乘次数分别为:7500和750000可 见,由于加括号的方法不同,使得连乘所用的数乘次数有很大差别。 对于n个矩阵的连乘积,令P(n)记连乘积的完全加括号数,则有如下 递归关系 P(n)={ ∑P(k)P(mn-k)n>1 (66) k=1 由此不难算出P=C(n-1),其中C表示 Catalan数: 1(2n =92(4"n32) (67) n+1(n 也就是说,P(n)是随n指数增长的,所以,我们不能希望列举所有可 能次序的连乘积,从中找到具有最少数乘次数的连乘积算法。事实上 矩阵连乘积问题具有最优子结构性质,我们可以采用动态规划的方 法,在多项式时间内找到最优的连乘积次序。 用A[ij表示连乘积AA+1…A,分析计算Aln]的一个最优次序 设这个计算次序在矩阵Ak和Ax+1之间将矩阵连分开,1≤kn,则完 全加括号方式为(A1A2…Ak)(Ak+…A),依此次序,我们先分别计算 A[1k]和A[k+ln],然后将计算的结果相乘得到A[ln]。可见,A[ln 的一个最优序所包含的矩阵计算子链A[k]和A[k+1n]的次序也一定 是最优的。也就是说,矩阵连乘问题具有最优子结构性质
以上的矩阵连乘则涉及到乘积次序问题，即加括号方法。例如 3 个 矩阵连乘的加括号方法有两种：((A1A2)A3)和(A1(A2A3))。设 A1，A2， A3 分别是 p0×p1，p1×p2，p2×p3 矩阵，则以上两种乘法次序所用的 数乘次数分别为：p0p1p2+p0p2p3和 p0p1p3+p1p2p3。如果 p0=10, p1=100, p2=5, p3=50, 则两种乘法所用的数乘次数分别为：7500 和 750000。可 见，由于加括号的方法不同，使得连乘所用的数乘次数有很大差别。 对于 n 个矩阵的连乘积，令 P(n)记连乘积的完全加括号数，则有如下 递归关系 − > = = ∑ − = 1 1 ( ) ( ) 1 1 1 ( ) n k P k P n k n n P n (6.6) 由此不难算出 P=C(n-1),其中 C 表示 Catalan 数： (4 / ) 2 1 1 ( ) 3 / 2 n n n n C n n = Ω + = (6.7) 也就是说，P(n)是随 n 指数增长的，所以，我们不能希望列举所有可 能次序的连乘积，从中找到具有最少数乘次数的连乘积算法。事实上， 矩阵连乘积问题具有最优子结构性质，我们可以采用动态规划的方 法，在多项式时间内找到最优的连乘积次序。 用 A[i:j]表示连乘积 AiAi＋1⋅⋅⋅Aj.分析计算 A[1:n]的一个最优次序。 设这个计算次序在矩阵 Ak 和 Ak+1 之间将矩阵连分开，1≤k<n，则完 全加括号方式为((A1A2⋅⋅⋅Ak)( Ak＋1⋅⋅⋅An))，依此次序，我们先分别计算 A[1:k]和 A[k+1:n]，然后将计算的结果相乘得到 A[1:n]。可见，A[1:n] 的一个最优序所包含的矩阵计算子链A[1:k]和A[k+1:n]的次序也一定 是最优的。也就是说，矩阵连乘问题具有最优子结构性质
如上三个例子都具有最优子结构性质,这个性质决定了解决此类 问题的基本思路是:首先确定原问题的最优值和其子问题的最优值之 间的递推关系,然后自底向上递归地构造出最优解。最优子结构性质 是最优化原理得以采用的先决条件。一般说来,分阶段选择策略确定 最优解的问题往往会形成一个决策序列。 Bellman认为,利用最优化 原理以及所获得的递推关系式去求解最优决策序列,可以使枚举数量 急剧下降。这里有一个问题值得注意:最优子结构性质提示我们使用 最优化原理产生的算法是递归算法,这很可能会增加时间与空间复杂 度。例如,用递归式直接计算矩阵连乘积A[ln]的算法 RecurMatrix Chain的时间复杂度将是2(2): 计算矩阵连乘的递归算法 int RecurMatrix Chain(int 1, int, j, int p) if(i-j return O int u=Recur Matrix Chain(i, 1) +RecurMatrix Chain(i+1j +p[i-1]*p[i]*p[] SGF=i for(int k=i+l; kj; k++) int t=RecurMatrix Chain(i, k) +Recur Matrix Chain(k+1, j +p[i-1]*p[i*p[j]
如上三个例子都具有最优子结构性质，这个性质决定了解决此类 问题的基本思路是：首先确定原问题的最优值和其子问题的最优值之 间的递推关系，然后自底向上递归地构造出最优解。最优子结构性质 是最优化原理得以采用的先决条件。一般说来，分阶段选择策略确定 最优解的问题往往会形成一个决策序列。Bellman 认为，利用最优化 原理以及所获得的递推关系式去求解最优决策序列，可以使枚举数量 急剧下降。这里有一个问题值得注意：最优子结构性质提示我们使用 最优化原理产生的算法是递归算法，这很可能会增加时间与空间复杂 度。例如，用递归式直接计算矩阵连乘积 A[1:n] 的算法 RecurMatrixChain 的时间复杂度将是 (2 ) n Ω ： 计算矩阵连乘的递归算法 int RecurMatrixChain(int i, int, j, int p) { if (i==j) return 0; int u=RecurMatrixChain(i, i) +RecurMatrixChain(i+1,j) +p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1; k<j; k++){ int t=RecurMatrixChain(i,k) +RecurMatrixChain(k+1,j) +p[i-1]*p[i]*p[j];
气t; s[[j}=k;} return u 如果用T(n)表示该算法的计算A[1n的时间,则有如下递归关系式 「O(1) 1 (n)≥ 1+∑(T(k)+7(m-k)+1)n>1 当n>1时T(m)≥1+(m-1)+∑7(k)+∑T(m-k)=n+2∑T(k), k=1 k=1 可用数学归纳法直接证明:T(n)≥2-1=92"),这显然不是我们所 期望的。 注意到,在用递归算法自顶向下求解具有最优子结构的问题时 每次产生的子问题并不总是新问题,有些问题被反复计算多次。动态 规划算法正是利用了这种子问题的重叠性质,对每一个问题只解 次,而后将其解保存在一个表格中,当再次需要解此问题时,只是简 单地用常数时间查看一下结果。通常,不同的子问题个数随输入问题 的大小呈多项式增长。因此,用动态规划算法通常只需要多项式时间, 从而获得较高的效率。所以,可用动态规划算法求解得的问题应具备 的另一个基本要素是子问题的重叠性。例如,在矩阵的连乘积问题中, 若用m]表示由第i个矩阵到第j个矩阵的连乘积所用的最少数乘 次数,则计算m[Iln时的子问题共有(n2)个。这是因为,对于
if (t = ≥ ∑ − = 1 1 1 ( ( ) ( ) 1) 1 (1) 1 ( ) n k T k T n k n O n T n 当n > 1时 ∑ ∑ ∑ − = − = − = ≥ + − + + = + 1 1 1 1 1 1 ( ) 1 ( 1) ( ) ( ) 2 ( ) n k n k n k T n n T k T n－k n T k ， 可用数学归纳法直接证明： ( ) 2 (2 ) n 1 n T n ≥ = Ω − ，这显然不是我们所 期望的。 注意到，在用递归算法自顶向下求解具有最优子结构的问题时， 每次产生的子问题并不总是新问题，有些问题被反复计算多次。动态 规划算法正是利用了这种子问题的重叠性质，对每一个问题只解一 次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简 单地用常数时间查看一下结果。通常，不同的子问题个数随输入问题 的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间， 从而获得较高的效率。所以，可用动态规划算法求解得的问题应具备 的另一个基本要素是子问题的重叠性。例如，在矩阵的连乘积问题中， 若用 m[i][j]表示由第 i 个矩阵到第 j 个矩阵的连乘积所用的最少数乘 次数，则计算 m[1][n]时的子问题共有 ( ) 2 Θ n 个。这是因为，对于
1≤i≤j≤n不同的有序对(j)对应于不同的子问题,不同子问题最多 只有(}+n=6(m2)个。用动态规划解此问题时,在计算过程中,保 存已解决的子问题答案,每个子问题只计算一次,而在后面用到时简 单地査一下,从而避免了大量的重复计算。 求矩阵连乘最优次序的动态规划算法 void Matrix Chain(int p, int n, int**m, int **s) for(int i=l; K<=n; 1++)m00=0; for (int r=2; r<=n;r++) for(int 1=1; 1<=n-r+1; 1++) ntj=i计+r-1; m[]]=m[i+1j+p[i-1*p[]*pl; SGF=1; for (int k=i+; k<; k++i int t=milk]+ m[k+10l+pi-1*p[k]"pl] if(t<mgli m[iG=t S[Dl=k;) 算法 Matrix chain的主要计算量取决于程序中对r,i和k的三重循环
1≤ i ≤ j ≤ n不同的有序对(i, j)对应于不同的子问题，不同子问题最多 只有 ( ) 2 2 n n n + = Θ 个。用动态规划解此问题时，在计算过程中，保 存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简 单地查一下，从而避免了大量的重复计算。 求矩阵连乘最优次序的动态规划算法 void MatrixChain(int p, int n, int * *m, int * *s) { for (int i=1; i<=n; i++) m[i][i]=0; for (int r=2; r<=n; r++){ for (int i=1; i<=n-r+1; i++) int j=i+r-1; m[i][j]= m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for (int k=i+1; k<j; k++){ int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j]; if (t< m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } 算法 MatrixChain 的主要计算量取决于程序中对 r, i 和 k 的三重循环
循环体内的计算量为O(1),三重循环的总次数是O(n3),所以,算法 的计算时间上界为O(n3)。 注意,上述算法只是明确给出了矩阵最优连乘次序所用的数乘次 数m[Iln],并未明确给出最优连乘次序,即完全加括号方法。但是 以s[i为元素的2维数组却给出了足够的信息。事实上,sij[]=k 说明,计算连乘积A[ij]的最佳方式应该在矩阵A和A+之间断开 即最优加括号方式为(A[ik]A[k+1j)。下面的算法 Traceback按算法 Matrix Chain计算出的断点信息s指示的加括号方式输出计算A[ij的 最优次序。 根据最优值算法构造最优解 Void Traceback(int i, int j, int**s if (i=ireturn Traceback(i, s[[, s); Traceback(S[0+1,j,s); cout<< Multiply a”≤i<“;”≤s[j[j] cout<<andA”≤(s[+1)<“”≤j;<endl 总结上面解矩阵连乘积问题,我们可以归纳出使用动态规划算法 的基本步骤 1.分析最优解的结构 在这一步中,应该确定要解决的问题应该是具有最小子结构性质
循环体内的计算量为 O(1)，三重循环的总次数是 O(n3 )，所以，算法 的计算时间上界为 O(n3 )。 注意，上述算法只是明确给出了矩阵最优连乘次序所用的数乘次 数 m[1][n]，并未明确给出最优连乘次序，即完全加括号方法。但是 以 s[i][j]为元素的 2 维数组却给出了足够的信息。事实上，s[i][j]=k 说明，计算连乘积 A[i:j]的最佳方式应该在矩阵 Ak和 Ak+1之间断开， 即最优加括号方式为(A[i:k])(A[k+1:j])。下面的算法 Traceback 按算法 MatrixChain 计算出的断点信息 s 指示的加括号方式输出计算 A[i:j]的 最优次序。 根据最优值算法构造最优解 Void Traceback(int i, int j, int * * s) { if (i==j) return; Traceback(i, s[i][j], s); Traceback(s[i][j]+1, j, s); cout << “Multiply A” << i << “,” << s[i][j]; cout << “and A” << (s[i][j] +1) << “,” << j; << endl; } 总结上面解矩阵连乘积问题，我们可以归纳出使用动态规划算法 的基本步骤： 1． 分析最优解的结构 在这一步中，应该确定要解决的问题应该是具有最小子结构性质
这是选择动态规划算法的基础。 2.建立递归关系 第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要 任务是递归地定义最优值,并建立该问题与其子问题最优值之间的 递归关系。例如在矩阵连乘积问题中,递归关系为 0 mU=1min(m+m/k+1B+m17/D}<j i≤k≤j 在经典O/1规划问题中的递归关系是 g(X)=max{g+1(X)g/+1(X-w+1)+p+1(68 在多段图问题中的递归关系是 COST(i,)=min c(, D)+COST(i+1, 0))(6.9) 这里j表示取V中的顶点 3.计算最优值 依据递归关系式可以自底向上的方式或自顶向下的方式进行计算, 在计算过程中保存已经解决的子问题答案。每个子问题只计算一次, 而在后面需要时只要简单査一下,从而避免大量的重复计算,最终获 得多项式时间的算法 4.造最优解 依据求最优值时记录的信息,构造出最优解。 上述归纳的4个阶段是一个整体,必要时才分步完成,很多时是统 一来完成的
这是选择动态规划算法的基础。 2． 建立递归关系 第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要 任务是递归地定义最优值，并建立该问题与其子问题最优值之间的 递归关系。例如在矩阵连乘积问题中，递归关系为 { } + + + < = = ≤ ≤ m[i] [k] m[k ] [j] p[i- ]*p[k]*p[j] i j i j m i j i k j min 1 1 0 [ ][ ] 在经典 0/1 规划问题中的递归关系是 g(X ) = max{g j+1(X ), g j +1(X − wj +1) + p j +1} (6.8) 在多段图问题中的递归关系是 ( , ) min { ( , ) ( 1, )} ,( , ) 1 COST i j c j l COST i l l Vi i l E = + + ∈ + ∈ (6.9) 这里 j 表示取 Vi中的顶点 j。 3． 计算最优值 依据递归关系式可以自底向上的方式或自顶向下的方式进行计算， 在计算过程中保存已经解决的子问题答案。每个子问题只计算一次， 而在后面需要时只要简单查一下，从而避免大量的重复计算，最终获 得多项式时间的算法。 4． 造最优解 依据求最优值时记录的信息，构造出最优解。 上述归纳的 4 个阶段是一个整体，必要时才分步完成，很多时是统 一来完成的
§2多段图问题 多段图是一种简单而经典的模型,它既能地反映了动态规划算法的基 本特征,而且在实际问题中有较多的应用。 ·乘0 由后向前的处理方法(动态规划方法) 由前向后的处理方法(备忘录方法) 根据(69)式,我们可以由后向前逐步确定各阶段中的顶点到汇顶点t 的最短路径。对于如上的5阶段网络图,上图中的红色字体标出了各 顶点到汇顶点t的最短距离。 事实上,我们也可以由前向后逐步确定由源顶点s到各阶段中顶
§2 多段图问题 多段图是一种简单而经典的模型，它既能地反映了动态规划算法的基 本特征，而且在实际问题中有较多的应用。 V1 V2 V3 V4 V5 7 4 4 6 9 7 4 4 9 2 5 7 2 S 7 5 3 2 2 t 16 3 18 1 11 5 2 7 5 15 11 6 5 8 由后向前的处理方法（动态规划方法） V1 V2 V3 V4 V5 9 13 4 6 9 9 4 4 7 2 5 7 2 S 7 11 3 14 2 t 3 3 1 16 11 5 2 10 5 2 11 6 16 8 由前向后的处理方法（备忘录方法） 根据(6.9)式，我们可以由后向前逐步确定各阶段中的顶点到汇顶点 t 的最短路径。对于如上的 5 阶段网络图，上图中的红色字体标出了各 顶点到汇顶点 t 的最短距离。 事实上，我们也可以由前向后逐步确定由源顶点 s 到各阶段中顶 1 2 4 6 9 10 11 12 3 7 8 5 1 2 4 6 9 10 11 12 3 7 8 5