文档介绍：§ 最短有向路
给定有向网络,设P为G中的一条有向路,P的权(或长):
问题:寻求有向网络中自某一指定点i到另一指定点j间的最短有向路
设有向网络G中不含非正有向回路,并且从点1到其余点都有有限长度的有向路,那么()有唯一有限解。
()
其中,和分别表示自点1到点j和点k的最短有向路的长度,表示弧的长度。
设是有向网络中自点1到点j的最短有向路的长度,并且对所有的,为有限值,若网络G中的点能编成如下的序号,使得若i<j,有且,但等号不同时成立或者且,即。则方程()可简化为
()
设是一个弧权为正值的有向网络,则在G中,任意一条最短有向路的长都大于它的真子有向路的长。G中自点1到其他各最短有向路的长可按大小排列如下
算法步骤:
第1步(开始)
置,,,,。
第2步(指出永久标号)
在T中寻找一点k,使得。置,。若,终止;否则,进行第3步。
第3步(修改临时标号)
对T中每一点j,置,然后返回第2步。
例:,其中每条弧上的数表示其权值。
② 3 ③

5 2 1 2
① 4 ⑥
3 7 4 6
④ 5 ⑤
解:
5
8
0
4
② 3 ③
5 2 1 2
① 4 ⑥
3 7 4 6
8
3
④ 5 ⑤
5
10
0
4
② 3 ③
5 2 1 2
① 4 ⑥
3 7 4 6
8
3
④ 5 ⑤
5
10
0
4
② 3 ③
5 2 1 2
① 4 ⑥
3 7 4 6
8
3
④ 5 ⑤
8
5
0
4
② 3 ③
5 2 1 2
① 4 ⑥
3 7 4 6
8
3
④ 5 ⑤
8
5
0
4
② 3 ③
5 2 1 2
① 4 ⑥
3 7 4 6
8
3
④ 5 ⑤
8
5
0
4
② 3 ③
5 2 1 2
① 4 ⑥
3 7 4 6
8
3
④ 5 ⑤
用反向追踪法确定最短有向路。