面向大规模道路网的最短路径近似算法

作者：张志然; 刘纪平^*; 仇阿根; 钱新林; 张福浩

来源：测绘学报, 2019, 48(01): 86-94.

• 大规模道路网
• 最短路径
• 节点重要性
• 网络划分

节点重要性对大规模道路网下最短路径的计算有着重要影响。本文提出了顾及节点重要性的最短路径估计方法,该方法基于Critic方法与复杂网络理论评价节点的重要性,结合限制策略实现网络划分,通过层次结构网络的构建,实现大规模道路网数据的有效化简和最短路径的快速有效计算。试验结果表明,该方法能够使中心节点均衡地分布于网络,更好地均衡划分后子网络的规模;随着限制参数的增大,网络规模逐渐降低,查询精度最高达到1.026,相比于单一指标和无限制参数的方法,本文方法显著降低了网络的规模,在最短路径的近似计算上保持了较高的准确性,为大规模复杂网络的近似分析提供分析思路。

• 单位
  中国测绘科学研究院; 河南省科学院地理研究所; 武汉大学