《最短路练习.ppt》由会员分享，可在线阅读，更多相关《最短路练习.ppt（29页珍藏版）》请在三一文库上搜索。
1、5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从点1出发，因L11=0，在点1处标记,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号权数；边变红。,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点与之间的最小权数（距离）者，找到之后：标号
2、；边变红。,2,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号权数；边变红。,2,3,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,4,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,4,5,1,2,7,5,6,3,4,2
3、,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,4,7,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,13,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,
4、13,对有向图同样可以用标号算法! 例 如下图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,v1,v9,
5、v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,6,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1
6、,4,0,3,4,6,6,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,9,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,9,