K则最短路径算法效率与精度评估

摘要：

精度和效率是决定最短路径算法实用价值的重要依据.对于K则最短路径问题,各种理论严密算法和有损算法的实用性分析是目前研究的薄弱环节.理论严密算法的实际运行效率比较及其有损算法的精度损耗与效率提高幅度的定量化一直未得到深入研究.针对这一问题,在对K则最短路径算法进行系统分类的基础上,分析了各种经典的理论严密算法和精度有损算法的特征与时间复杂度,结合实际城市路网数据对各种K则最短路径算法的运行效率和精度进行了测试和比较.结果显示,与有损算法相比,理论严密的K则最短路径算法普遍缺乏实用性,只有多重标号算法适合于某些要求精度无损的应用;而一些有损K则最短路径算法以较小的精度损失换取了较大幅度的效率提高,尤以双向搜索算法最具应用推广价值.

关键词：K则最短路径算法、交通网络、效率、精度

所属期刊栏目：14

分类号：TP391;U491(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863项目2006AA12Z209,2007AA12Z241;中国科学院知识创新工程前沿基金项目CXIOG-D04-02

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

页数：共7页

页码：1677-1683