§5.3 多阶段有向图中的最短路问题 5个部分：
{}{
}{}{}{}E D D D C C B B B A ,,,,,,,,,32121321 初态、终态、始态、末态、状态I
赋权多阶段有向图
图5.7
解： 8356676m i n ),(1=⎪⎭
⎪⎬⎫⎪⎩⎪⎨⎧+++=E C l ，31)(D C d =， 53264min ),(2=⎭
⎬⎫
⎩⎨
⎧++=E C l ，32)(D C d =， 85386min ),(3),(6min ),(211=⎭⎬⎫
⎩⎨⎧++=⎭
⎬⎫⎩⎨
⎧++=E C l E C l E B l ,21)(C B d =，
类似：125785min ),(7),(5min ),(212
=⎭⎬⎫
⎩⎨⎧++=⎭
⎬⎫⎩⎨⎧++=E C l E C l E B l ,22)(C B d =， 95481m i n ),(4),(1m i n ),(213=⎭⎬⎫⎩⎨⎧++=⎭
⎬⎫⎩⎨
⎧++=E C l E C l E B l ,.,)(213C C B d =
99812481min ),(8),(4),(1min ),(321=⎪
⎭
⎪
⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=E B l E B l E B l E A l ，1)(B A d =，
因此：最短路 .,,,,321E D C B A 路长：9
原则：最短路中每节为最短。

§5.4 摹矩阵 表上作业法
摹矩阵的乘规则：乘法=对应元素乘积的和；将乘积摹为求和，将和摹为取小 ),,(⊗⊕S 对应),,(⨯+R ⊕叫摹和，⊗叫摹积
零元素：z ：在非负数中为最小，加什么等于什么：{}a z a z a ==⊕,min 单位元素1：e ：乘什么等于什么：z z a z a =+=⊗；a e a e a =+=⊗ 半域),,(⊗⊕S ：不可逆
极小代数：)min,,(+R 代数；+∞=z ，0=e ；{}{}R R S =∞+= ⎥
⎦
⎤
⎢⎣⎡--=⎥⎦⎤⎢⎣⎡⊕⎥⎦⎤⎢
⎣⎡--723213426251753312对应元素取小（摹和） ⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⊗⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡574624361344348732513 {
}763,34,48min 633448=+++=⊗⊕⊗⊕⊗， 关于最长路问题：只需在最短路问题基础上作三点修改 一、)max ,,(+R 即),,(+∨R 是一个半域，也称为极大代数 {}
{}∞-= 实数R ，单位元素0，零元素∞- 二、摹乘法为：“相加取大”
三、零元素为∞-，而非∞+
也可规定路长为各边路长之积，且要求最小 可以在)min,,(⨯R 上计算就可以了。

因此多阶段有向图的最短路问题的求解过程可以采用：表上作业法
表5.1
添入参数，采用摹矩阵用算可得
表5.2
§5.5 决策数确定型动态规划 §5.5.1 Bellman 最优化原理 Bellman 最优化原理：
最优策略有以下的性质：无论其初态和初始决策如何，其今后的决策序列对以第一个决策所形成的状态所为初态的系统而言，必须构成最优策略。

§5.5.2 Bellman 递推公式
{}10,)(),(min )(1-≤≤+=+n j t f t x g x f j j （5.5）
如果终态只有一个元素v，还有
f
(
v
)
（5.6）n
（5.5）叫做Bellman递推公式，（5.6）是它的边界条件。