★各递推结果 第4段cOST(4,9)=c(9,12)=4 COsT(4,10)=c(10,12)=2 COsT(4,11)=c(11,12)=5 第3段cOST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7 cOST(3,7)=min4+cOST(4,9),3+CosT(4,10}=5 COST(38)=mn{5+COST(4,10),6+COST(4,11)}=7 第2段COsT(2,2)=min{4+COST(36),2+COST(3,7) 1+COST(38)}=7 COsT(2,3)=9 COsT(2,4)=18 COsT(2,5)=15 第1段cOsT(1,1)=min{9+coST(2,2),7+COST(23) 3+COST(2,4),2+COST(2,5) 16 S到t的最小成本路径的成本=16
2021/2/20 26 ★各递推结果 第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5 第3段 COST(3,6) = min{6+COST(4,9),5+COST(4,10)} = 7 COST(3,7) = min{4+COST(4,9),3+COST(4,10)} = 5 COST(3,8) = min{5+COST(4,10),6+COST(4,11)} = 7 第2段 COST(2,2) = min{4+COST(3,6) , 2+COST(3,7), 1+COST(3,8)} = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15 第1段 COST(1,1) = min{9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)} = 16 S到t的最小成本路径的成本 ＝ 16
★最小成本路径的求取 记D(i,j)=每一COST(i,j)的决策 即,使c(j,1)+COST(i+1,1)取得最小值的1值 例:D(3,6)=10,D(3,7)=10D(3,8)=10 D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8 D(1,1) 根据D(1,1)的决策值向后递推求取最小成本路径: ●v2=D(1,1)=2 V3=D(2,D(1,1))=7 D(3,D(2,D(1,1)=D(3,7)=10 故由s到t的最小成本路径是:1→2→7→1012 2021/2/20
2021/2/20 27 ★ 最小成本路径的求取 记 D(i,j)＝每一COST(i,j)的决策 即，使c(j,l)+COST(i+1,l)取得最小值的l值。 例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(1,1) = 2 根据D(1,1)的决策值向后递推求取最小成本路径： ● v2=D(1,1)=2 ● v3 = D(2,D(1,1)) = 7 ● v4 = D(3,D(2,D(1,1))) = D(3,7) = 10 故由s到t的最小成本路径是：1→2→7→10→12
3)算法描述 ★结点的编号规则 源点s编号为1,然后依次对V2、V…Vk-中的结点编号, 汇点t编号为n。 目的:使对COST和D的计算仅按n-1,n-2,…,1的次序计 算即可,无需考虑标示结点所在段的第一个下标。 ★算法描述 2021/2/20
2021/2/20 28 3) 算法描述 ★ 结点的编号规则 源点s编号为1,然后依次对V2、V3…Vk-1中的结点编号， 汇点t编号为n。 目的：使对COST和D的计算仅按n-1,n-2,…,1的次序计 算即可，无需考虑标示结点所在段的第一个下标。 ★ 算法描述
算法4.1多段图的向前处理算法 procedure FGRAPH(E, k,n, P) ∥输入是按段的顺序给结点编号的,有n个结点的k段图。E是边 集,c(ij)是边<i>的成本。P(1:k)带出最小成本路径∥ real CosT(n); integer D(n-1), P(k), r,j, k, n COsT(n)←0 forj←n-1to1by-1do∥计算cOST()∥ 设是具有性质:习,r>∈E且使c(,)+COST()取最小值的结点 COsT()←c()+cOST(r) D()←「∥记录决策值∥ repeat P(1)←1;P(K)←n forj←2tok-1do∥找路径上的第个结点∥ P()←D(P(-1)∥回溯求出该路径∥ repeat end fGraPh 2021/2/20
2021/2/20 29 算法4.1 多段图的向前处理算法 procedure FGRAPH(E,k,n,P) //输入是按段的顺序给结点编号的，有n个结点的k段图。E是边 集，c(i,j)是边<i,j>的成本。P(1:k)带出最小成本路径// real COST(n); integer D(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 P(1)←1; P(k)←n for j←2 to k-1 do //找路径上的第j个结点// P(j) ←D(P(j-1)) //回溯求出该路径// repeat end FGRAPH
算法的时间复杂度 若G采用邻接表表示,总计算时间为: O(n+e 2021/2/20 30
2021/2/20 30 算法的时间复杂度 若G采用邻接表表示，总计算时间为： (n + e)