路网中基于地理位置和区域封闭性的最短路径的查询算法

针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。