王 亚，任 燕，夏林元

1.遵义师范学院信息工程学院，贵州遵义563000

2.中山大学地理科学与规划学院，广东广州510275

交通运输网络是对提供物资输送且具有点线连通的网状地物的模型简化.节点实体、弧段实体及网络拓扑关系构成交通运输网络的基本模型要素.交通运输网络分析最常见的应用场景是交通运输网络的最短（或最优）路径分析.

在交通运输网络的最短路径算法研究中，基于道路交通网络的研究是最广泛的，文献[1-2]对道路交通网络的最短路径算法按目标向导和层次化两种类型进行了讨论.目标导向方法主要是通过引导路径的搜索方向来减少算法的搜索空间，该方法并不改变数据本身的性状.层次化方法则通过道路网的等级属性以及交叉口（可视为交通运输网络的节点）的连通性将一个网络分割成为相互连通的多层次网络，高层次的网络弧段量依次变少，最低层次的网络包含全部的弧段和节点实体，因此算法可以在不同的层次网络间切换搜索路径，从而降低搜索空间.上述文献虽然给出了算法间的性能比较，但算法的实现效率跟实际所采用的数据结构和内容密切相关，而这些文献并没有进行深入的研究.文献[3]在有向带权联通图的数据基础上对Dijkstra 算法进行了改进，针对不联通两点可能形成死循环的问题设计了相应的退出机制，并提出了如何求取最短路径上节点的相邻点的方法.该方法采用通用……