动态规划中的最长路径问题
题目：设图G=(V, E)是一个带权有向连通图，如果把顶点集合V 划分成k个互不相交的子集Vi（2≤k≤n, 1≤i≤k），使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m（1≤i＜k,1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。
多段图的最长路径问题是求从源点到终点的最大代价路径
由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。
不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。
假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。
一个多段图
用c（u，v）表示边上的权值，将从源点s到终点t的最长路径记
为d(s, t)，则从源点0到终点9的最长路径d(0, 9)由下式确定：d(0, 9)=max{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}这是最后一个阶段的决策，它依赖于d(1, 9)、d(2, 9)和d(3, 9)
d(1, 9)=max{c14+d(4, 9), c15+d(5, 9) }
d(2, 9) =max{c24+d(4, 9), c25+d(5, 9) , c26+d(6, 9) }
d(3, 9) =max{c35+d(5, 9), c26+d(6, 9) }
这是倒数第二阶段的式子它分别依赖于d(4, 9)，d(5, 9)，d(6, 9) d(4, 9)= max{c47+d(7, 9), c48+d(8, 9) }
d(5, 9)= max{c57+d(7, 9), c58+d(8, 9) }
d(6, 9)= max{c67+d(7, 9), c68+d(8, 9) }
这是倒数第三阶段的式子它们依赖于d(7, 9)，d(8, 9)
d(7, 9)= c79=7
d(8, 9)= c89=3
再往前推
d(6, 9)=max{c67+d(7, 9), c68+d(8, 9)}
= max {6+7, 5+3}=13(6→8)
d(5, 9)= max {c57+d(7, 9), c58+d(8, 9)}
= max {8+7, 6+3}=15(5→8)
d(4, 9)= max {c47+d(7, 9), c48+d(8, 9)}
= max {5+7, 6+3}=12(4→7)
d(3, 9)= max {c35+d(5, 9), c36+d(6, 9)}
= max {4+15, 7+13}=20(3→6)
d(2,9)= max {c24+d(4,9), c25+d(5,9), c26+d(6, 9)}
= max {6+12, 7+15, 8+13}=22(2→5)
d(1, 9)= max {c14+d(4, 9), c15+d(5, 9)}
=min{9+12, 8+15}=23(1→5)
d(0, 9)= max {c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}
= max {4+23, 2+22, 3+20}=27(0→3)
最后，得到最长路径为0→1→5→7→9，长度为27。
下面考虑多段图的最长路径问题的填表形式。
用一个数组cost[n]作为存储子问题解的表格，cost[i]表示从顶点i到终点n-1的最长路径，数组path[n]存储状态，path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点。
则：
cost[i]=max{cij+cost[j]}
(i≤j≤n且顶点j是顶点i的邻接点) （式6.7）path[i]=使cij+cost[j]最大的j （式6.8）
程序算法
多段图算法：
Procedure FGRAPH（E,k,n,P）
//输入是按段的顺序给结点编号的，有n个结点的k段图。
E是边集，c（i，j）是边<i，j>的成本。
P（1：k）是最大成本路径。
// real COST(n),integer(n-1),P(k),r,j,k,n COST(n)<-0
for j<-n-1 to 1 by -1 do //计算COST（j）//
设r是一个这样的结点，（j，r E且使c（j，r）+COST（r）取最大值COST（j）<- c（j，r）+COST（r）;D(j)<-r;Repeat //向前对j-1进行决策// P（1）<-1; P（k）<-n;
for j<-2 to k-1 do // 找路径上的第j个节点// P（j）<-D(P(j-1));repeat; end FGRAPH
四.程序关键代码
void fgraph(int cost[],int path[],int d[]) //使用向前递推算法求多段图的最长路径{ int r,j,temp,min; for(j=0;j<=n;j++) cost[j]=0; for(j=n-1;j>=1;j--) { temp=0;
min=c[j][temp]+cost[temp]; //初始化大值for(r=0;r<=n;r++) {
if(c[j][r]!=MIN) {
if((c[j][r]+cost[r])<max) //找到最大的r { min=c[j][r]+cost[r]; temp=r;
}
}
}
cost[j]=c[j][temp]+cost[temp];
d[j]=temp; }
path[1]=1; path[k]=n;
for(j=2;j<k;j++)
path[j]=d[path[j-1]];
}
void bgraph(int bcost[],int path1[],int d[])//使用向后递推算法求多段图的最短路径{ int r,j,temp,min; for(j=0;j<=n;j++) bcost[j]=0; for(j=2;j<=n;j++) { temp=12;
min=c[temp][j]+bcost[temp]; //初始化最大值for(r=0;r<=n;r++) {
if(c[r][j]!=MIN) { if((c[r][j]+bcost[r])<max) //找到最大的r {
min=c[r][j]+bcost[r];
temp=r;
} } }
bcost[j]=c[temp][j]+bcost[temp]; d[j]=temp;
}
path1[1]=1; path1[k]=n;
for(int i=4;i>=2;i--) { path1[i]=d[path1[i+1]];
}
void main()
{
int cur=-1; int cost[13],d[12],bcost[13]; int path[k]; int path1[k];
cout<<"\t\t\t动态规划解多段图问题"<<endl; cout<<"\n\n"; init(cost);
fgraph(cost,path,d);
cout<<"输出使用向前递推算法后的最长路径:\n\n"; for(int i=1;i<=5;i++) { cout<<path[i]<<" ";
}
cout<<"\n";
cout<<endl<<"最长路径为长度:"<<cost[1]<<endl;
cout<<"\n";
cout<<"\n输出使用向后递推算法后的最长路径:\n\n"; bgraph(bcost,path1,d); for(i=1;i<=5;i++) { cout<<path1[i]<<" ";
}
cout<<"\n"; cout<<endl<<"最长路径为长度:"<<bcost[12]<<endl;
cout<<"\n";
实验小结
动态规划最长路径问题和动态规划的最短路径很相似，我们用递归的的方法，递推最优化的最长路径长度，让时间复杂度更为简单，我们再设计算法时，也要注意怎样实现这个过程，如何找到它的前驱结点和后继结点，我们通过连接矩阵或你连接表的方式查找。