运筹学 operations research 第三章图与网络分析 [5,v3] [6,v2] 2 [O [3,v1 [12v5 10 4 [1,v1 [10v5 [9,vs 此时终点vg已标号[12v5],则12即为v1→vn的最 短距离,反向追踪可求出最短路http://www.tju.edu.cn 第三章 图与网络分析 [0, v 1 ] [1, v 1 ] [3, v 1 ] [5, v 3 ] [6, v 2 ] [9, v 5 [10, v 5 ] ] [12, v 5 ] 10 此时终点 v 9已标号[12, v 5 ]，则12即为 v 1 → v n的最 短距离，反向追踪可求出最短路 v 2 v 1 v 3 v 4 v 5 v 6 v 7 v 8 v 9 1 6 3 2 2 2 2 6 6 1 3 4 10 3 4