改进的Dijkstra 标号法在城乡规划中小学选址的应用＊

曾丽群，单国彬

（1.柳州工学院土木工程系，广西 柳州 545616；2.柳州市公共资源服务交易中心，广西 柳州 545616）

1 Dijkstra 标号法

1.1 Dijkstra 最短距离标号法

1959 年，迪杰斯特拉提出的标号法是最短路径问题的最好求解方法，用于计算1 个节点到其他节点的最短路径。基本思路为：将各顶点用可行的路径进行连线，得到1 个赋权图G。假设V1为起点，Vk为终点，则V1在图G 中有k-1 种路径可以达到终点Vk，之后依次计算Vi（i=2，3，4，…，k）到V1的距离T（Vi），则minT（Vi）对应的路径为最优路径。

1.2 最短距离标号法的应用

近年来，Dijkstra 最短距离标号法主要应用于自驾游最短线路、最佳导航线路、人员疏散路径、最佳交通线路、应急救援及避灾线路选择等最短线路规划和最优路径选择中[1-5]，在应用中是以使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径（空间）距离总和的最小值作为选址判定的依据。

城乡规划中涉及消防站、医院、中小学等公共服务设施的选址，主要考虑服务半径即服务范围，可以应用标号法求出公共服务设施的最优选址，其质量判据为最大服务距离最小化[6-10]。其基本思想为：在赋权有向图G 中，对图中的每条边都赋予1 个权值（距离），图中的各顶点分别用Vi（i=1，2，…，k）表示。在图G 中选择其中的任一点Vi作为拟选址点，求出Vi到其余各顶点的最短距离，计为dij（j=1，2，…，k），这样就得到K 行、K 列的距离矩阵Dk×k。在距离矩阵Dk×k中，先求出每行元素的最大值max（di），之后再求出每行max（di）的最小值min［max（di）］，该最小值min［max（di）］所对应的元素dij、所在列的列号j、所在顶点Vj即为最优选址点，如果最小值min［max（di）］对应的元素不唯一，则说明最优选址不唯一，最优选址为多个。……