例：动态规划解最短路径问题

•例：动态规划解最短路径问题:步骤(1)、(2)已实现。最优子结构：从起点到终点的最短路径包含了该路径上各点到终点的最短路径。递归公式：设v为图中一个顶点，V],v2，...,Vm为v的直接后继，cost(v)表示V到终点的最短路径长度，c[u,w]表示边＜u,w＞上的权"为终点,则cost满足如下递归公式：min{c[v,v]+cost(v)},v丰t且v有后继1<i<miicost(v)=<0,v=tS,v。t且vcost(v)=步骤(3)计算最优值(求最短路径长度):设有向网G含n个顶点，用邻接矩阵c[1..n,1..n]表示，起点为s,终点为t。有关信息的保存：数组cost[1..n]:存储子问题的解。（cost[i]表示从顶点i到终点t的最短路径长度。）数组succ[1..n]:存储最短路径的有关信息。（succ[i]表示顶点i到终点t的最短路径上顶点i的直接后继。）原问题的最优值为cost[s]。（1）自底向上的迭代算法关键：根据递归公式确定迭代顺序（即子问题的求解顺序）。原则：计算cost[i]时，顶点i的所有后继的cost值应先计算。计算顺序：按图G的逆拓扑排序顺序。算法SHORTEST_ROUTE_LEN1输入：有向网G的顶点数n,邻接矩阵c[1..n,1..n],起点s和终点t,1<=s,t<=n。输出：G的从起点s到终点t的最短路径长度cost[s]和最短路径有关信息的数组succ[1..n]。〃对图G拓扑排序，结果存于数组a[1..n]中。toposort(c,n,a)j=nwhilea[j]<>tj=j-1〃找出j使得a[j]=t。fori=j+1toncost[a[j]]=s//排除无关的顶点。cost[t]=0〃从终点开始迭代。whilea[j]<>sj=j-1;k=a[j];i0=0;min=sfori=1tonifc[k,i]+cost[i]<mintheni0=i;min=c[k,i]+cost[i]endifendforcost[k]=min;succ[k]=i0endwhileendSHORTEST_ROUTE_LEN1(2)自顶向下的递归算法关键：对每个子问题标记是否计算过，同一子问题只在第一次递归调用时计算并存储结果。标记：未求出cost[i]时，cost[i]=-1。算法SHORTEST_ROUTE_LEN2输入：有向网G的顶点数n,邻接矩阵c[1..n,1..n],起点s和终点t,1<=s,t<=n。输出：G的从起点s到终点t的最短路径长度minlen和最短路径有关信息的数组succ[1..n]。fori=1toncost[i]=-1minlen=routelength(s)endSHORTEST_ROUTE_LEN2过程routelength(j)//求G中从顶点j到终点t的最短路径长度cost[j]并返回，〃同时求该路径上各顶点的直接后继存于数组succ中。ifcost[j]=-1then//cost[j]还未求出ifj=tthencost[j]=0elsemin=8;i0=0fori=1tonifc[j,i]<8then〃顶点i为顶点j的后x=routelength(i)〃求i到t的最短路径长度ifc[j,i]+x<minthenmin=c[j,i]+x;i0=iendifendifendforcost[j]=min;succ[j]=i0;endifendifreturncost[j]endroutelength步骤(4)构造最优解(设存在从起点s到终点的路径)算法SHORTEST_ROUTE输入:有向网G的从起点s到终点t的最短路径信息数组succ[1..n]输出：有向网G的从起点s到终点t的最短路径。i=1;b[i]=swhileb[i]<>tb[i+1]=succ[b[i]]i=i+1endwhile输出b[1