文档介绍：§ 最短有向路
Linear Programming
运筹学课件
①
⑤
④
②
③
开始
修改
修改2
①
⑥
⑤
④
②
③
例:用Dijkstra算法求解下图所示有向网络中自点1到其他各点的最短有向路。
3
8
5
8
4
①
⑥
⑤
④
②
③
0
解:标出定点1的永久标号0,再标出其它点的临时标号
步骤
8
5
3
8
5
①
⑥
⑤
④
②
③
0
8
4
把点4的临时标号改为永久标号,再修改其它临时标号
3
①
⑥
⑤
④
②
③
0
4
10
步骤
8
5
8
3
5
①
⑥
⑤
④
②
③
0
4
10
把点6的临时标号改为永久标号,再修改其它临时标号
3
①
⑥
⑤
④
②
③
0
4
10
步骤
8
8
3
5
①
⑥
⑤
④
②
③
0
4
10
把点2的临时标号改为永久标号,再修改其它临时标号
3
5
①
⑥
⑤
④
②
③
0
4
8
8
3
5
①
⑥
⑤
④
②
③
0
4
8
8
3
5
①
⑥
⑤
④
②
③
0
4
8
把点3的临时标号改为永久标号,再修改其它临时标号
8
3
5
①
⑥
⑤
④
②
③
0
4
8
8
3
5
①
⑥
⑤
④
②
③
0
4
8
把点5的临时标号改为永久标号,用反向追踪法找出点1到其它点的最短有向路
作业:
P233 6,7,9