基于路标的最短路径长度快速估计算法

摘要：

针对大规模复杂网络中最短路径精确算法计算复杂的问题,提出一种基于路标的最短路径长度快速估计算法——SSPS算法.论证了SSPS算法的估计精度优于已有的Potamias算法；采用多种路标选择策略,使用多个数据集对比了SSPS算法与Potamias算法的性能.实验结果表明:SSPS算法的估计精度优于Potamias算法,且在最简单的随机路标选择策略中表现出良好的估计精度,可以较好地应用于大规模复杂网络最短路径长度的估算中.

关键词：复杂网络、近似算法、路标方法、最短路径问题

所属期刊栏目：27

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61070199,61103189;国家863课题资助项目2011AA01A103

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

页数：共8页

页码：96-102,118