最短路径算法:分类体系与研究进展

最短路径算法是计算机科学与地理信息科学等领域的研究热点。本文首先讨论了平面图的搜索策略 ,然后从问题类型、网络类型和实现方法 3方面对最短路径算法进行了系统的分类 ,从理论上比较了近年来所提出的各种具有较高效率的串行最短路径算法的时间复杂度 ,并对国内外一些相关研究进行了综合评述。结合城市交通网络的实验结果 ,作者对几种应用最为广泛的串行最短路径算法的运行效率进行了分析和评价 ,最后对最短路径算法在实时化和并行化方面的发展进行了讨论。