第3章 动态规划

1第3章动态规划动态规划算法的基本要素举例1矩阵连乘问题举例2凸多边形最优三角剖分举例3最长公共子序列举例4多段图的最短路径问题举例50-1背包问题举例6资源分配问题2动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题。nn/4n/4n/4n/4区别：经分解得到的子问题往往不是互相独立的。问题：用分治法求解，有些子问题被重复计算多次。3保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算，从而得到多项式时间算法。这就是动态规划算法。解决方法找出最优解的性质，并描述其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。动态规划算法的基本步骤货郎担问题假设用邻接矩阵C={cij}存储。分别求从城市i出发的哈密尔顿回路，最后求n条回路的最小值。货郎担问题的动态规划函数最优值：d(i,V-{i})货郎担问题动态规划函数的递归表示4个城市1、2、3、4，邻接矩阵如下表。动态规划解货郎担问题解：以从城市1出发为例，求哈密尔顿回路，其它城市同理。第一阶段

d(1,{2,3,4})=min{c12+d(2,{3,4}),c13+d(3,{2,4}),c14+d(4,{2,3})}第二阶段d(2,{3,4})=min{c23+d(3,{4}),c24+d(4,{3})}d(3,{2,4})=min{c32+d(2,{4}),c34+d(4,{2})}d(4,{2,3})=min{c42+d(2,{3}),c43+d(3,{2})}

计算过程第3阶段

d(3,{4})=c34+d(4,ф)=2+3=5{3,4,1}d(4,{3})=c43+d(3,ф)=5+6=11{4,3,1}d(2,{4})=c24+d(4,ф)=3+3=6{2,4,1}d(4,{2})=c42+d(2,ф)=7+5=12{4,2,1}d(2,{3})=c23+d(3,ф)=2+6=8{2,3,1}d(3,{2})=c32+d(2,ф)=4+5=9{3,2,1}计算过程

回溯第2阶段

d(2,{3,4})=min{2+5,3+11}=7{2,3,4,1}d(3,{2,4})=min{4+6,2+12}=10{3,2,4,1}d(4,{2,3})=min{7+8,5+9}=14{4,3,2,1}

回溯第1阶段

d(1,{2,3,4})=min{3+7,6+10,7+14}=10{1,2,3,4,1}计算过程动态规划解货郎担问题求解过程示意图12动态规划算法举例1：矩阵连乘问题给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的。由于乘法满足结合律，故计算矩阵的连乘可以有不同的计算次序。其计算次序可以用加括号的方式确定。假设有4个矩阵：A,B,C,D乘法：16000乘法：10500乘法：36000乘法：87500乘法：3450013矩阵连乘问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的乘法次数最少。14矩阵连乘方法1：枚举法列举出所有可能的计算次序，并计算出每一种计算次序所需要的乘法次数，从中找出一种乘法次数最少的计算次序。

时间复杂度分析：对于n个矩阵的连乘，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：结论：P(n)随n的增长呈指数增长，不是高效算法。115矩阵连乘方法1：动态规划算法将矩阵连乘积AiAi+1...Aj

简记为A[i:j]，i≤j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为：

(AiAi+1...Ak）(Ak+1Ak+2...Aj)计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。

16（1）分析最优解的结构关键特征：计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求最优解的显著特征。17（2）建立递归关系假设计算A[i:j]（1≤i≤j≤n）所需要的最少乘法次数为m[i,j]，则原问题的最优值为m[1,n]。当i=j时，A[i:j]=Ai，因此m[i,i]=0，i=1,2,…,n当i<j时，m[i][j]=m[i][k]+m[k+1][j]+pi-1×pk×pj

k∈{i,i+1,...,j-1}可以递归地定义m[i,j]为：18（3）计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应不同的子问题，因此不同子问题的个数最多只有：可以看出，在递归计算时，有许多子问题被重复计算。19intrecurMatrixChain(intp[],inti,intj){if(i==j)return0;intu=∞;for(intk=i;k<j;k++){intt=recurMatrixChain(p,i,k)+recurMatrixChain(p,k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}returnu;}20出现重复计算是该问题用动态规划算法求解的又一个显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查找一下，从而可以避免大量地重复计算，最终得到多项式时间的算法。21计算最优解的动态规划算法假设Ai的维数为pi-1×pi，则输入序列为{p0,p1,p2,...,pn}p[n+1]记录每个矩阵的维数;m[i,j]记录AiAi+1...Aj相乘的代价（乘法次数）;s[i,j]记录取得最优代价所断开的点k。22具有自底向上的计算特征：如果计算m[i,j]，仅需要小于j-i+1个的矩阵乘积。即计算长度为L的矩阵相乘代价仅依赖于小于L长度的矩阵相乘代价。算法思路：按照长度递增(1,2,...n)计算m[i,j]代价。算法matrixChain，首先计算出m[i,i]=0,i=1,2,…,n。然后，根据递归式，按矩阵链长递增的方式依次计算：m[i，i+1],i=1,2,…,n-1,(矩阵链长度为2）；m[i，i+2],i=1,2,…,n-2,(矩阵链长度为3）…；在计算m[i，j]时，只用到已计算的m[i，k]和m[k+1，j].231234567812345671234561234512341231211234567812345678m长度（个数）m[3,6]:m[3,3]+m[4,6]m[3,4]+m[5,6]m[3,5]+m[6,6]r24计算最优解的动态规划算法伪语言voidmatrixChain(intp[],intm[][NUM+1],ints[][NUM+1],intn){//n是当前矩阵个数，NUM是最大矩阵个数处理矩阵长度为1的代价（m[i,i]=0）；for(intr=2;r<=n;r++)//长度从2~nfor(inti=1;i<=n-r+1;i++){//m[i][i+r-1]intj=i+r-1;

寻找min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}->m[i][j],

k->s[i][j];

(

i≤k<j)}}25算法voidmatrixChain(intp[],intm[][NUM+1],ints[][NUM+1]){//p数组包含n+1元素for(inti=1;i<=n;i++)m[i][i]=0;//将长度为1的代价赋为0for(intr=2;r<=n;r++)//长度从2~nfor(inti=1;i<=n-r+1;i++){//从第1行开始~n-r+1行为止intj=i+r-1;m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];//k=i,m[i][i]=0可以省略s[i][j]=i;for(intk=i+1;k<j;k++){intt=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;}}}}算法描述了矩阵填充的过程：r为当前斜线起始列号（长度）i控制当前斜线元素行号J控制当前斜线元素列号26A1A2A3A4A5A6303535

1515

55

1010

2020

25算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的三重循环。循环体内的计算量为O(1)，三重循环的总次数为O(n3)。因此算法计算时间上界为O(n3)。算法占用的空间为O(n2)。p0p1p2p3p4p5p63035155102025举例：给定一个6个矩阵的矩阵链：27打印矩阵的运算次序voidprintOptimalParens(int

s[][NUM+1],inti,intj){if(i==j){cout<<"A"<<i;}else{cout<<"(";printOptimalParens(s,i,s[i][j]);printOptimalParens(s,s[i][j]+1,j);cout<<")”; }}输出结果：((A1(A2A3))((A4A5)A6))28总结：动态规划算法的基本要素（1）最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。（2）重叠子结构在利用递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。29动态规划算法举例2：凸多边形最优三角剖分用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。30多边形的三角剖分就是将多边形分割成互不相交的三角形的弦的集合T。在凸多边形P的三角剖分T中,各弦互不相交,且集合T已达到最大。在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。31给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得三角剖分中各个三角形的权值之和最小。32一个带括号的表达式可以用一棵二叉树表示其计算顺序，称为表达式的语法树。例如，((A1(A2A3))(A4(A5A6)))对应的语法树是语法树33三角剖分的结构及其相关问题凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。除（v0,v6）外，其余边构成叶子结点，弦构成内部结点。34三角剖分的结构及其相关问题矩阵连乘积中的每个矩阵Ai对应凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i<j，对应矩阵连乘积A[i+1:j]。35凸多边形最优三角剖分问题：给定凸边形p={v0,v1,...vn-1}，以及定义在由多边形的边和弦组成的三角形上的权函数w，要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权之和最小。w(vivjvk)=|vivj|+|vjvk|+|vkvi|36（1）最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。证明（反证法）：如果凸(n+1)边形P={v0,v1,…,vn}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：v0vkvn+{v0,v1,…,vk}+{vk,vk+1,…,vn}可以断言，由T确定的两个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。37（2）最优三角剖分的递归结构定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。假设将退化的多边形{vi-1,vi}的权值定义为0。最终需要计算的凸(n+1)边形P的最优权值为t[1][n]。38利用最优子结构性质递归地计算t[i][j]。当j-i≧1时，凸子多边形至少有3个顶点。由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。需要在j-i个位置中选出使t[i][j]达到最小的k。39t[i][j]可递归地定义为：（3）计算最优值创建数组s[i][j]，用于存放与vi-1和vj一起构成三角形的第3个顶点位置。与矩阵连乘相仿，最优值可以通过数组s得到。4041voidminWeightTriangulation(intn,intt[][NUM],ints[][NUM]){//t[i][j]存放vi-1…vj之间凸多边形最优剖分权值//s[i][j]存放最优剖分令一个顶点的位置

初始化t[][]=0；for(intr=2;r<=n;r++)//计算r凸边形的最优剖分2..nfor(inti=1;i<=n-r+1;i++){intj=i+r-1;

//计算i->j之间边数为r的最优剖分权值及位置k//并分别将结果存放在t[i][j]和s[i][j]中}}42voidminWeightTriangulation(intn,intt[][NUM],ints[][NUM]){for(inti=1;i<=n;i++)t[i][i]=0;//初始化t[][]for(intr=2;r<=n;r++)//计算r凸边形的最优剖分for(inti=1;i<=n-r+1;i++){intj=i+r-1;//计算i->j之间的最优值及位置kt[i][j]=t[i+1][j]+w(i-1,i,j);s[i][j]=i;for(intk=i+1;k<i+r-1;k++){intu=t[i][k]+t[k+1][j]+w(i-1,k,j);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}}消耗空间：O(n2)消耗时间：O(n3)43动态规划算法举例3：最长公共子序列在生物工程应用中，我们经常要比较两个DNA序列的相似性，在软件工程领域也经常比较两个软件版本，以便确定版本的变化，所有这些相似性比较问题，都涉及最长公共子序列问题。若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，Z={B，C，D，B}是X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。44公共子序列给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是X和Y的公共子序列。最长公共子序列问题：给定2个序列

X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。45（1）分析最优子结构假设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则(1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。46证明(1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。

反证法：假设zk≠xm,则{z1,z2,...,zk,xm}是X和Y的长度为k+1的公共子序列。与假设Z是X和Y的最长公共子序列矛盾。（2）（3）类似。由最长公共子序列问题的最优子结构性质可知:要找出X={x1,x2,x3,…,xm}和Y={y1,y2,y3,…,yn}的最长公共子序列，可按以下方式递归计算：当xm=yn时，找出xm-1和yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的最长公共子序列。当xmyn时，必须解两个子问题：即找出xm-1和y的一个最长公共子序列及x和yn-1的一个最长公共子序列。这两个公共子序列中较长者即为x和y的最长公共子序列。4748（2）递归关系由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，Xi和Yj的最长公共子序列是空序列。故此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：c[0...m][0...n]49（3）计算最优值由于在所考虑的子问题中，总共有θ(mn)个不同的子问题，采用递归算法会随着序列长度的增长，时间复杂性成指数递增，而采用动态规划算法自底向上计算最优值可提高算法的效率。b[i][j]记录计算子序列的方式。c[i][j]记录Xi和Yj的最长公共子序列的长度。50intlcsLength(charx[],chary[],int

b[][NUM],intm,intn){int*c=创建C数组;

初始化c[i][0]，c[0][i]为0;

for(inti=1;i<=m;i++){

for(intj=1;j<=n;j++){

if(xi-1==yj-1){//第一种情况c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}

elseif(c[i-1][j]>=c[i][j-1]){//第2,3种情况c[i][j]=c[i-1][j];b[i][j]=2;}

else{c[i][j]=c[i][j-1];b[i][j]=3;}}}returnc[m][n];}时间复杂度O(mn)51intlcsLength(charx[],chary[],intb[][NUM],intm,intn){intc[m+1][n+1];for(inti=0;i<=m;i++)c[i][0]=0;for(inti=0;i<=n;i++)c[0][i]=0;

for(inti=1;i<=m;i++){

for(intj=1;j<=n;j++){

if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}

elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}

else{c[i][j]=c[i][j-1];b[i][j]=3;}}}returnc[m][n];}时间复杂度O(mn)52构造最长公共子序列(打印最长公共子序列）voidlcs(inti,intj,charx[],intb[][NUM]){

if(i==0||j==0)return;

if(b[i][j]==1){

lcs(i-1,j-1,x,b);cout<<x[i-1];}

elseif(b[i][j]==2)lcs(i-1,j,x,b);

elselcs(i,j-1,x,b);}每次运行都使i或j减1，所以时间复杂度为O(m+n)。53

#include<cstring>intmain(){char*x="ABCBDAB";char*y="BDCABA"; intxlen=strlen(x);intylen=strlen(y);intb[NUM1+1][NUM2+1];intlen=lcsLength(x,y,b,xlen,ylen);lcs(xlen,ylen,x,b);return0;}运行结果：BCBA54运行结果：BCBA55运行结果：BCBA5600000000000yj:xmy1y2ynx1x2xii012nm120firstsecond填表的顺序：沿着箭头先填充最上面一行，然后填充接下来的行5700000000000yj:DACFABxiji012nm120矩阵cStep[i,j]:它告诉我们要获得最优结果应该如何选择如果xi=yj

cStep[i,j]=“↖”（1）如果 nZ[i-1,j]≥nZ[i,j-1]

cStep[i,j]=

“↑”（2）否则

cStep[i,j]=“←”（3）33CDc[i,j-1]c[i-1,j]nLCS(sX,sY,nA,nB)1

for

i←1to

nA

do

nZ[i,0]←02

for

j←0to

nB

do

nZ[0,j]←03

for

i←1to

nA

do4

for

j←1to

nB

do5

if

xi=yj6

then

nZ[i,j]←c[i-1,j-1]+17 cStep[i,j]←“↖”8

elseif

nZ[i-1,j]≥nZ[i,j-1]9

then

nZ[i,j]←nZ[i-1,j]10 cStep[i,j]←“↑”11

else

nZ[i,j]←nZ[i,j-1]12 cStep[i,j]←“←”13

return

nZandcStep58运行时间:(nA*nB)举例X=(B,D,C,A,B,A)Y=(A,B,C,B,D,A,B)590126345yjBDACAB51203467DABxiCBAB00000000000000

0

0

0

1

1

1

1

1

1

1

2

2

1

1

2

2

2

2

1

1

2

2

3

3

1

2

2

2

3

3

1

2

3

2

3

4

1

2

2

3

4

4如果xi=yj

cStep[i,j]=“

”如果 nZ[i-1,j]≥nZ[i,j-1]

cStep[i,j]=“

”否则

cStep[i,j]=“

”找出最长共同子序列sLCS(cStep,sX,i,j)1

if

i=0orj=02thenreturn3if

cStep[i,j]="↖"4then

sLCS(cStep,X,i-1,j-1)+xi5elseif

cStep[i,j]="↑"6then

sLCS(cStep,X,i-1,j)7else

sLCS(cStep,X,i,j-1)6061动态规划算法举例4：

多段图的最短路径问题多段图定义：给定有向连通带权图G=(V,E,W)，如果将顶点集合V划分成k个互不相交的子集Vi，1≤i≤k，k≥2,使得E中的任何一条边(u,v)，必有u∈Vi,v∈Vi+m，m≥1，则称这样的图为多段图。62多段图令|V1|=|Vk|=1,称s∈V1为源点，t∈Vk为汇点。st63首先，根据定义，将图划分成若干个段；随后，从左向右逐段为顶点编号（源点编号为0，汇点编号为n-1）64多段图最短路径问题：求从源点s到达汇点t的最小花费的通路。st65（1）分析最优子结构假设从顶点i到汇点t的最短通路为：（i,j,……,t）则（j,……,t）一定是从顶点j到汇点t的最短通路。证明：反证法。66（2）递归关系首先，确定k-1段的所有顶点到达汇点t的花费最小的通路。cost[i]：存放顶点i到汇点t的最小花费path[i]：存放最小花费通路上，i顶点的直接后继顶点编号随后，利用k-1段的计算结果，计算k-2段的所有顶点到达汇点t的花费最小的通路。以此类推，直到确定源点s到汇点t的花费最小的通路。67递归关系cost[i]=min{cij+cost[j]}i<j<n0i=n-1ijjj…...…...…...t68（3）计算最优值创建数组path，并在数组path中存放目前确定的花费最小通路的情况。path[i]存放从i顶点到达汇点t花费最小通路上顶点i的直接后继顶点编号。69最小花费通路：0->2->3->5->8->9012345678253588899path70算法为语言描述：（1）初始化cost[i]=最大值，cost[n-1]=0;path[i]=-1（2）for(i=n-2;i>=0;i--)计算cost[i],path[i]（3）根据path计算花费最小的通路，

并存放在数组route中

令i=0;route[0]=0;

重复计算下列公式，直到route[i]=n-1

i++;route[i]=path[route[i-1]];710123456789∞∞∞∞∞∞∞∞∞00123456789-1-1-1-1-1-1-1-1-1-1costpath初始化720123456789∞∞∞∞∞∞∞∞300123456789-1-1-1-1-1-1-1-19-1costpathi=8:730123456789∞∞∞∞∞∞∞7300123456789-1-1-1-1-1-1-199-1costpathi=7:740123456789∞∞∞∞∞∞87300123456789-1-1-1-1-1-1899-1costpathi=6:750123456789∞∞∞∞∞987300123456789-1-1-1-1-18899-1costpathi=5:760123456789∞∞∞∞9987300123456789-1-1-1-188899-1costpathi=4:770123456789∞∞∞139987300123456789-1-1-1588899-1costpathi=3:780123456789∞∞14139987300123456789-1-13588899-1costpathi=2:790123456789∞1514139987300123456789-153588899-1costpathi=1:800123456789151514139987300123456789253588899-1costpathi=0:81有向连通带权图采用邻接矩阵表示#defineVEX_NUM?#defineEDGE_NUM?#defineMAX_VALUE32767usingnamespacestd;classGraph{private: intvex_num;//顶点数目 intedge_num;//边数目 intadj[VEX_NUM][VEX_NUM];//邻接矩阵public: Graph(){vex_num=VEX_NUM;edge_num=EDGE_NUM;

} intgetVexNum(){returnvex_num;} intgetEdgeNum(){returnedge_num;} voidsetVexNum(intnum){vex_num=num;} voidsetEdgeNum(intnum){edge_num=num;} intgetWeight(inti,intj){returnadj[i][j];} voidsetWeight(inti,intj,intw){adj[i][j]=w;}};82voidfgraph(GraphG,intcost[],intpath[]){intn=G.getVexNum();

for(inti=0;i<n;i++){//初始化 cost[i]=MAX_VALUE; path[i]=-1;

}cost[n-1]=0;for(inti=n-2;i>=0;i--){//计算cost[],path[] for(intj=i+1;j<n;j++){ intp=G.getWeight(i,j); if(p!=MAX_VALUE){//如果有边 if(G.getWeight(i,j)+cost[j]<cost[i]){//判断是否更小cost[i]=G.getWeight(i,j)+cost[j]; path[i]=j;

}

}

}}}时间复杂性O(n2)空间复杂性O(n)83//根据path[]，计算最终结果，并存入数组route[]中voidresult(intcost[],intpath[],introute[],intn,int&minCost){

for(inti=1;i<n;i++){ route[i]=-1;

} inti=0;route[0]=0; while((route[i]!=n-1)&&(path[i]!=-1)){ i++;route[i]=path[route[i-1]];

} minCost=cost[0];}i=8:cost[8]=c89+cost[9]=3+0

path[8]=9i=7:cost[7]=c79+cost[9]=7+0path[7]=9i=6:cost[6]=min{c67+cost[7],c68+cost[8]}=min{6+7,5+3}=8

path[6]=8i=5:cost[5]=min{c57+cost[7],c58+cost[8]}=min{8+7,6+3}=9

path[5]=8i=4:cost[4]=min{c47+cost[7],c48+cost[8]}=min{5+7,6+3}=9

path[4]=8i=3:cost[3]=min{c35+cost[5],c36+cost[6]}=min{4+7,7+8}=13