问题的描述 1）二分检索树定义
二分检索树Ｔ是一棵二元树，它或者为空，或者其每个 结点含有一个可以比较大小的数据元素，且有：
·Ｔ的左子树的所有元素比根结点中的元素小； ·Ｔ的右子树的所有元素比根结点中的元素大； ·Ｔ的左子树和右子树也是二分检索树。 注： ·二分检索树要求树中所有结点的元素值互异
29
二分检索树
COST(n)0
for jn -1 to 1 by –1 do
设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
计算出COST(j)的值， 并找出一条最小成本 路径
for j2 to k-1 do
12
4.2 多段图
多段图向前处理的算法
– 设P(i, j)是一条从Vi中的节点j 到汇点t 的最小 成本路径，COST(i, j)表示这条路径的成本， 根据向前处理方法有公式4.5：
13
多段图的向前处理算法
因为，若<j, t> ∈E成立,有COST(k-1,j)=c(j,t), 若<j, t> ∈E不成立，则有COST(k-1,j)=∞，所以 可以通过如下步骤解式公式（4.5），并求出 COST(1,s)。 首先对于所有j∈Vk-2，计算COST(k-2, j)，然后对 所有的j∈Vk-3，计算计算COST(k-3, j)等等，最后 计算出计算COST(1, s)
BCOST(2，4)=3； BCOST(2，5)=2；
21
V1
V2
V3
V4
V5
24
9
1
3
