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

摘要：

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

关键词：最短路径算法、分类、评价、进展

所属期刊栏目：30

分类号：P208(一般性问题)

资助基金：国家科技攻关项目96-B02-03-05

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：269-275