【摘要】：令lij=∑wij=min的计算称其为最短路问题。算法 最短路问题的计算方法采用双标号法。最短路问题的标号算法特别适合于复杂网络的计算机处理，因为无论点有多少，每一步的计算程序都是一样的。
3.1.1 定义与算法
（1）定义 对于G=（V，E），vi，vj∈G，则lij为vi到vj之间的距离。令lij=∑wij=min的计算称其为最短路问题。式中wij为权数，wij可以是距离、时间或费用等。
（2）算法 最短路问题的计算方法采用双标号法。所谓双标号法指用已知点vi为第一标号，用计算值作为第二标号，具体步骤如下：
第一步：令起始点（vi）处的标号值vi=0；
第二步：计算其余点处的标号值：
第三步：最短路的确定，从图的终止点起逆向按第一标号值即可确定，且最短路{lij}min=终止点处的第二标号值bn。
3.1.2 工程算例
【例5.15】 求图5.34（有向图）中从v1到v7的最短路。
(www.xing528.com)
图5.34 某工程最短路的双标号法计算结果
解：（1）令第一个（起始）点处的标号v1=0。
（2）计算其余点处的标号值（第二标号值）aj=[vi+wij]min，以第5点处为例，第5点处的标号计算如下，其余点处标号值的计算成果已标于图5.34中
（3）最短路见图5.34中带箭头线路所示。即：
{lij}min=v1→v3→v5→v7→v9
标号算法对有向图和无向图都适用，不过有向图只能沿一定的方向取生长线。
最短路问题的标号算法特别适合于复杂网络的计算机处理，因为无论点有多少，每一步的计算程序都是一样的。
用笔算解最短路问题时，每一步的运算过程不必一一写出，可以把每一步各点的标号列成表，再在图上标出P标号和相应的最短路即可。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
