多段图问题

来源:百度知道 编辑:UC知道 时间:2024/06/09 08:15:23
这是一个算法问题 (用VC++写)
向前算法为
line proceduce FGRAPH(E,k,n,p)
//输入是按段的顺序给结点标号的,有n个结点的k段图.E是边集,c(i,j)是边(i,j)的成本.P(1:k)是最小成本路径//
COST(n),integerD(n-1),P(k),r,j,k,n
COST(0)←0
for j←n-1 to 1 by -1 do
设r是一个这样的结点,(j,r)∈E且使c(j,r)+COST(r)取最小值
COST(j)←c(j,r)+COST(r)
D(j)←n
for j←2 to k-1 do
P(1)←D(P(j-1))
repeat
end FGRAPH

难啊
向前算法为
line proceduce FGRAPH(E,k,n,p)
//输入是按段的顺序给结点标号的,有n个结点的k段图.E是边集,c(i,j)是边(i,j)的成本.P(1:k)是最小成本路径//
COST(n),integerD(n-1),P(k),r,j,k,n
COST(0)←0
for j←n-1 to 1 by -1 do
设r是一个这样的结点,(j,r)∈E且使c(j,r)+COST(r)取最小值
COST(j)←c(j,r)+COST(r)
D(j)←n
for j←2 to k-1 do
P(1)←D(P(j-1))
repeat
end FGRAPH