梁泽宇:标号法——顺序维护的有力工具.pdf

标号法(labeling method)寻找最短路线问题的最优方案的一个有效方法。采取顺加取大的方法。 基本步骤为: 1.先标出离起点最近的一段，将距离数字分别写在该段线终点上方的方格内. 2.在标下一段时，正要标号的某点到该段已标号的各点的距离，分别加上已标号点的数字而取其中最大者，这就是某点到下一点的最短距离.将距离数字 [1] 填人某点上方方格内，并用直线连结起来表示某点到终点的最短路线. 3.继续按顺推过程计算，直至终点为止. 这里是从后向前标的，也可以从前向后标.