5
A 7 4
B
6 4
D
6 F
5
C
3
E
1
前一部分实际上是Bellman最优化原理的直接结果； 后一部分中Bellman方程解的唯一性可以用反证法证明（略）
11
最短路树（树形图）
如果将定理中的条件“只含正有向圈”改为“不含负有向圈”： 上述最短路仍然存在；STEP1.

u j ui wij , pred( j) i .
17
正费用网络（Dijkstra算法）
引理5.2 在上述Dijkstra 算法中, （1）对于S中的任一顶点 j ，其距离标号 uj 是从起点 s 到该顶点 j 的最短路路长；
（2）对于 S 中的任一顶点j，其距离标号uj是从起点s出发，只经 过S中的顶点到达顶点j 的最短路路长.
归纳法. 算法开始时结论成立. 设直到迭代的第k步，上述结论(1)(2)成立.
O 如果采用邻接表表示法，可首先计算各节点的入度； (m) 然后找入度为零者编号； O(n) 去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描 该去掉的节点的出弧）； O(m) 依次类推。 O ( m n)
2
该算法自然可以用来判断有向图是否无圈图.
13
最短路算法 -
5.2.2 无圈网络
(5.9) (5.10)
5
B
6 4
D
6 F (结束)
(开始) A
7
4
C
5 3 E
1
5
项目网络不含圈, 其最长路问题和最短路问题都是可解的.
最短路问题
s
t
给定有向网络N，弧（i，j）对应的权又称为弧长（或费用）. 对于其中的两个顶点s，t，以s为起点和t为终点的有向路称为 s-t有向路，其所经过的所有弧上的权（或弧长、费用）之和 称为该有向路的权（或弧长、费用）. 所有s-t有向路中权(或弧长、费用)最小的一条称为s-t最短路. 对于有向网络中的一个圈，定义它的权为圈上所有前向弧上的 权的和, 减去圈上所有反向弧上的权. 权为正的圈称为正圈; 权为负的圈称为负圈; 权为0的圈称为零圈. 对一个有向圈， 它的权就是圈上所有弧上的权的和. 本章的 圈一般都是指有向圈, 我们直接将正有向圈简称为“正圈”， 负有向圈简称为“负圈”， 零有向圈简称为“零圈”, 而 6 “无圈”指的是不存在有向圈.
正费用网络（Dijkstra算法）
u S STEP0. (初始化) 令S= ，=V， s u1 0, pred(s) 0 ；对V 中 的顶点j(j s)令初始距离标号 u j .
STEP1. 如果S=V, 则uj为节点s到节点j的最短路路长(最短路可 以通过数组pred所记录的信息反向追踪获得), 结束. 否则继续 STEP2. STEP2. 从 S 中找到距离标号最小的节点i，把它从 S 删除，加 入S. 对于所有从i出发的弧 (i, j ) A , 若 u j ui wij ，则令
t 1 t 1
可以证明：一定存在满足条件 I t 1 xt 0(1 t T )
的最优解.
3
可以只考虑
xt 0, dt , dt dt 1,, dt dt 1 dT
单产品、无能力限制的批量问题 记wij为第i时段生产量为 xi d i d i 1 d j 时所导致的费用 (包括生产准备费、生产费和库存费), 即 w s c x j 1h I
14
最短路算法 – 例
例5.4 计算如下网络(图5.4 (a))中从节点A到所有其它节点的最短路.
1
A -1 B 1 A -1 B 1 E -1
E 5 3 1
-2 D 4 C 1 -1 3
i2
1
2 E 5 3 1
-2 4 4 5
-2
D
计算过程: u 1 =0, u 2 min{u i wi 2 } =min{0+1}=1,
其中 I t d t 1 d i 2 d j (i t j 1)
ij
i
i i

t i
t t
网络：从所有节点i到j (> i)连一条弧, 弧上的权为wi,j-1 , 如T=4时：
w12
w11 w22
w23 3
w33
w34
1
2
4
w24
w44
5
w13
w14
4
例5.3 计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法)
基本思想：对于V 中每一个顶点j，赋予两个数值（通常称为“标号”）： 一个是距离标号uj ，记录的是从起点到该顶点的最短路长度的上界；
另一个是前趋标号pred（j），记录的是当起点s到该顶点j 的一条路长取
到该上界时，该条路中顶点j 前面的那个直接前趋（节点）.
算法通过不断修改这些标号，进行迭代计算. 当算法结束时， 距离标号表示的是从起点到该顶点的最短路长度. 迭代进行计算的过程中，所有顶点实际上被分成了两类： 一类是离起点 s 较近的顶点，它们的距离标号表示的是从点s到 该顶点的最短路长度，因此其标号不会在以后的迭代中再被改 变（称为永久标号）； 一类是离起点 s 较远的顶点，它们的距离标号表示的只是从点 到该顶点的最短路长度的上界，因此其标号还可能会在以后的 16 迭代中再被改变（称为临时标号）.
s1
10
2
1
3
-1
起点s到顶点的最短路长度分别是us=u1=0， u2 =10， u3 =11 但此时只要u3 = u2+1 11 (us=u1=0)就可以满足Bellman方程. 如 us=u1=0， u2 =8， u3 =9 等 对于一般的网络，Bellman方程只是最短路长度必须满足的必 要条件，而不是充分条件； 对于只含正有向圈的连通有向网络，它才是充要条件.
对偶问题为
max(ut us ) s.t. u j ui wij , (i, j ) A.
(5.4) (5.5)
根据互补松弛条件, 当x和u分别为原问题和对偶问题的最优解 时: xij (u j ui wij ) 0, (i, j) A. (5.6) 9
Bellman方程
1
最短路问题的例子和意义
S
T
许多实际问题都可以转化为最短路问题
其有效算法经常在其它网络优化问题中作为子算 法调用
2
最短路问题的例子 - 单产品、无能力限制的批量问题
例5.1 （Single-level Uncapacitated Lotsizing） 某工厂生产某种产品用以满足市场需求,且已知在时段t中的市 场需求为dt . 在某时段t, 如果开工生产, 则生产开工所需的生 产准备费为st , 单件产品的生产费为ct .在某时段t期末, 如果有 产品库存, 单件产品的库存费为ht . 假设初始库存为0, 不考虑 能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且 使总费用最小? （Wagner – Whitin，1958） 假设在时段t, 产品的生产量为xt , 期末产品的库存为It (I0 =0); 用二进制变量yt表示在时段t工厂是否进行生产准备. T T 假设费用均非负，则在最优解中 I 0 I T 0 ，即 xt d t
12
最短路算法 -
5.2.2 无圈网络
引理5.1 （拓扑排序，Topological Ordering ）设有向图D不 含回路,则D的顶点总可以重新编号,使得 i j, (i, j ) A .
如果采用邻接矩阵表示法，可首先计算各节点的入度； O(n ) 然后找入度为零者编号； O(n) 去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描 该去掉的节点的对应行） ； O(n n) O(n2 ) 依次类推。 O(n2 )
大型复杂工程项目(Project)往往被分成许多子项目,子项目之 间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间 完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每 一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分.
网 络 优 化
Network Optimization
/netopt
清华大学课号：40420213（本），70420133（研）
第5章 最短路问题(Shortest Path Problem)
清华大学数学科学系 谢金星 办公室：理科楼1308# （电话：62787812） Email:jxie@ /faculty/~jxie
最短路问题 – 两点说明
最长路问题可以转化为最短路问题，把弧上的费用反号即可. 必须指出：目前为止，一切最短路算法都只对不含负有向圈 的网络有效. 对于含负有向圈的网络，最短路问题是NP困难的. 因此，本章中除非特别说明，一律假定网络不包含负有向圈.
无向网络上的最短路问题一般可以转化为有向网络上的问题.
当某弧(i,j)位于最短路上时， 即变量xij>0时, 一定有 u j ui wij
如果u为对偶问题最优解,易知u+c (c为任意实数)仍为最优解.
不妨令 us=0 ，则u的具体数值就可以唯一确定了. 相当于对节点j赋予的一个实数值uj（通常称为 “标号”），在 us=0时表示的正好是节点s到节点j的最短路的长度. Bellman方程(最短路方程、动态规划基本方程 )
8
5.2.1 Bellman方程
min
( i , j )A
w x
ij ij
(5.1) i s, i t, i s, t , (5.3) (5.2' )