一种基于双向搜索的K则最优路径算法

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于双向搜索的K则最优路径算法

高松, 陆锋, 段滢滢

文章导航 > 武汉大学学报 ( 信息科学版) > 2008 > 33(4): 418-421

高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报 ( 信息科学版), 2008, 33(4): 418-421.

引用本文:

高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报 ( 信息科学版), 2008, 33(4): 418-421.

GAO Song, LU Feng, DUAN Yingying. A Kth Shortest Path Algorithm Implemented with Bi-directional Search[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.

Citation:

GAO Song, LU Feng, DUAN Yingying. A Kth Shortest Path Algorithm Implemented with Bi-directional Search[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.

一种基于双向搜索的K则最优路径算法

高松^1,2,
陆锋¹,
段滢滢^1,2

¹中国科学院资源与环境信息系统国家重点实验室,北京市朝阳区大屯路甲11号100101;²中国科学院研究生院,北京市石景山区玉泉路甲19号,100049

基金项目: 国家863计划资助项目(2006AA12Z209)，中国科学院知识创新工程前沿资助项目(CXIOG-D04-02)，中国科学院知识创新工程重点方向性资助项目(KZCX2-YW-308)

作者简介:
高松,硕士生,研究方向为交通地理信息系统技术。

中图分类号: P208

A Kth Shortest Path Algorithm Implemented with Bi-directional Search

¹LREIS,Institute of Geographic Sciences and Natural Resources Research,CAS,11A Datun Road,Beijing 100101,China;²Graduate University of Chinese Academy of Sciences,19A Yuquan Road,Beijing 100049,China

Funds: 国家863计划资助项目(2006AA12Z209)，中国科学院知识创新工程前沿资助项目(CXIOG-D04-02)，中国科学院知识创新工程重点方向性资助项目(KZCX2-YW-308)

摘要: 提出了一种基于双向搜索策略的K则最优路径算法,以改进的Dijkstra最优路径算法为基础,从起点和终点同时搜索,分别构造正序和逆序最优路径树,计算网络中两点之间的多条参考K则最优路径。详细描述了算法设计思想和运行过程,分析了算法的时间复杂度,并通过实际路网验证了算法的效率和精度。
- K则最优路径算法 /
- 双向搜索 /
- Dijkstra算法
Abstract: A new Kth shortest path algorithm based on bidirectional search is set forward in this paper.Based on the classical Dijkstra's shortest path algorithm,the presented algorithm conducts the path searching both from the source and destination nodes at the same time,and constructs the shortest path trees in positive and reverse sequence alternately so to populate several reasonable shortest paths between the start and destination nodes.The principle and implementation of the algorithm is described in detail and time complexity is analyzed.The efficiency and accuracy are verified with a real road network.
- Kth shortest path algorithm /
- bidirectional search /
- Dijkstra's algorithm

[1]	杨安秀, 吴自银, 阳凡林, 宿殿鹏, 冯成凯, 许方正. 面向多波束测深数据的双向布料模拟自动滤波算法 . 武汉大学学报 ( 信息科学版), 2022, 47(4): 517-525. doi: 10.13203/j.whugis20190419
[2]	徐铮, 邹滨, 郑忠, 蒲强, 杨忠霖, 孙国庆. 一种健康出行路径动态搜索算法与系统实现 . 武汉大学学报 ( 信息科学版), 2019, 44(1): 145-152. doi: 10.13203/j.whugis20150749
[3]	杨军, 林岩龙, 张瑞峰, 王小鹏. 一种大规模点云k邻域快速搜索算法 . 武汉大学学报 ( 信息科学版), 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
[4]	雷海军, 谢莲花, 何业军, 朱国云. AVS菱形搜索运动估计算法优化 . 武汉大学学报 ( 信息科学版), 2012, 37(3): 374-377.
[5]	严瑞, 龙毅, 郑玥, 余明朗. 顾及地形起伏的步行最优路径分析算法 . 武汉大学学报 ( 信息科学版), 2012, 37(5): 564-568.
[6]	马娟, 方源敏, 赵文亮, 冯瑜瑾. 利用空间微分块与动态球策略的k近邻搜索算法研究 . 武汉大学学报 ( 信息科学版), 2011, 36(3): 358-362.
[7]	黄飞江, 卢晓春, 吴海涛, 边玉敬. 基于星间距离变化的动态双向时间同步算法 . 武汉大学学报 ( 信息科学版), 2010, 35(1): 13-16.
[8]	鲁敏, 张金芳. 栅格地形的最优路径分析 . 武汉大学学报 ( 信息科学版), 2010, 35(1): 59-63.
[9]	赵俭辉, 龙成江, 丁乙华, 袁志勇. 一种基于立方体小栅格的K邻域快速搜索算法 . 武汉大学学报 ( 信息科学版), 2009, 34(5): 615-618.
[10]	王毅, 张良培, 李平湘. 基于自动搜索和光谱匹配技术的训练样本纯化算法 . 武汉大学学报 ( 信息科学版), 2007, 32(3): 216-219.
[11]	孙文彬, 赵学胜. 基于Quaternary编码的球面三角格网邻近搜索算法 . 武汉大学学报 ( 信息科学版), 2007, 32(4): 350-352.
[12]	郑春燕, 郭庆胜, 刘小利. 基于禁忌搜索算法的点状要素注记的自动配置 . 武汉大学学报 ( 信息科学版), 2006, 31(5): 428-431.
[13]	廖楚江, 蔡忠亮, 杜清运, 王长耀. 基于最少换乘的公交最优路径算法的设计与实现 . 武汉大学学报 ( 信息科学版), 2006, 31(10): 904-907.
[14]	陈玉敏, 龚健雅, 史文中. 多级道路网的最优路径算法研究 . 武汉大学学报 ( 信息科学版), 2006, 31(1): 70-73.
[15]	郑年波, 李清泉, 徐敬海, 宋莺. 基于转向限制和延误的双向启发式最短路径算法 . 武汉大学学报 ( 信息科学版), 2006, 31(3): 256-259.
[16]	阳仁贵, 欧吉坤, 王振杰, 赵春梅. 用遗传算法搜索GPS单频单历元整周模糊度 . 武汉大学学报 ( 信息科学版), 2005, 30(3): 251-254.
[17]	李订芳, 章文, 牛艳庆. 基于粗糙集的缺失数据循环搜索重建算法 . 武汉大学学报 ( 信息科学版), 2005, 30(11): 1016-1019.
[18]	邵振峰, 李德仁, 程起敏. 基于航空立体影像对的复杂房屋三维拓扑重建 . 武汉大学学报 ( 信息科学版), 2004, 29(11): 999-1003.
[19]	陆锋, 周成虎, 万庆. 基于层次空间推理的交通网络行车最优路径算法 . 武汉大学学报 ( 信息科学版), 2000, 25(3): 226-232.
[20]	乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现 . 武汉大学学报 ( 信息科学版), 1999, 24(3): 208-212.

WeChat

点击查看大图

计量

文章访问数: 847
HTML全文浏览量: 75
PDF下载量: 510
被引次数: 0

一种基于双向搜索的K则最优路径算法

¹中国科学院资源与环境信息系统国家重点实验室,北京市朝阳区大屯路甲11号100101;²中国科学院研究生院,北京市石景山区玉泉路甲19号,100049

基金项目: 国家863计划资助项目(2006AA12Z209)，中国科学院知识创新工程前沿资助项目(CXIOG-D04-02)，中国科学院知识创新工程重点方向性资助项目(KZCX2-YW-308)

作者简介:
高松,硕士生,研究方向为交通地理信息系统技术。

收稿日期: 2008-02-24
修回日期: 2008-02-24
刊出日期: 2008-04-05

中图分类号: P208

关键词:

K则最优路径算法 /

摘要: 提出了一种基于双向搜索策略的K则最优路径算法,以改进的Dijkstra最优路径算法为基础,从起点和终点同时搜索,分别构造正序和逆序最优路径树,计算网络中两点之间的多条参考K则最优路径。详细描述了算法设计思想和运行过程,分析了算法的时间复杂度,并通过实际路网验证了算法的效率和精度。

English Abstract

高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报 ( 信息科学版), 2008, 33(4): 418-421.

引用本文:

高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报 ( 信息科学版), 2008, 33(4): 418-421.

GAO Song, LU Feng, DUAN Yingying. A Kth Shortest Path Algorithm Implemented with Bi-directional Search[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.

Citation:

GAO Song, LU Feng, DUAN Yingying. A Kth Shortest Path Algorithm Implemented with Bi-directional Search[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

我要投稿

投稿攻略

联系我们

二维码