上海安吉汽车物流运输方式及线路的优化(2)

（4）v2为刚得到P标号的点，考察边（v2,v4），（v2,v5）的端点v4,v5 T(v4)=min*T(v4),P(v2)+L24+=min*+∞ ,75+78+=153

T(v5)=min*T(v5),P(v2)+L25+=min*+∞ ,75+132+=207

（5）比较T标号，T(v3)最小，所以令P(v3)=122，并记录路径（v1,v3）

（6）考虑点v3，有

T(v4)=min[T(v4),P(v3)+L34]=min[153,122+132]=153

T(v5)=min[T(v5),P(v3)+L35]=min[207 ,122+133]=207

（7）全部T标号中，T(v4)最小，令P（v4）=153，并记录路径（v2,v4）

（8）考察点v4

T(v6)=min*T(v6),P(v4)+L46+=min*+∞ ,153+93+=246

（9）全部T标号中，T(v5)最小，所以P(v5)=207，并记录路径（v2,v5） T(v6)=min[T(v6),P(v5)+L56]=min[246 ,207+107]=246

综上可以看出，路径v1---v2---v4---v6为从v1到v6的最短路径。最短路径全长246，即从天津到石家庄的最短路线是从天津至霸州，经过保定，最终到达石家庄。

以上是Dijkstra算法所求的最短路线。

上面是在主干线的前提下进行的细部路线的细化分析，只是涉及了陆运的天津到石家庄，其他细化的路线可以参考上部进行分析，以选择最短的路线。