典型城市路网中的椭圆最短路径算法

摘要：

提出了一种高效可靠的限制搜索区域的最优路径算法.该算法是基于典型城市路网的共同特征,而不是某个特定城市的统计信息提出的,它可以应用在不同的城市路网中.针对从源站点到目的站点不同的欧式距离,算法分别在两类不同大小的椭圆内搜索最短路径.理论计算和实验结果都表明,当源站点和目的站点相距较远时,与椭圆限制搜索区域算法相比,该算法可以降低33%-47%的时间复杂度,而不会影响查询结果的准确性.

关键词：迪杰斯特拉算法、欧式距离、最短路径、限制搜索区域、典型城市路网

所属期刊栏目：31

分类号：U491.2+1(交通工程与公路运输技术管理)

资助基金：国家自然科学基金60532030;教育部新世纪优秀人才支持计划NCET-08-0333;山东省自然科学基金Y2007G10

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

页数：共7页

页码：1158-1164