结合概率搜索定界的入度统计最短路径算法

交通运输系统工程与信息 ›› 2011, Vol. 11 ›› Issue (6): 169-174.

结合概率搜索定界的入度统计最短路径算法

敬明，邓卫*

东南大学交通学院，南京 210096

收稿日期:2011-08-05 修回日期:2011-09-19 出版日期:2011-12-25 发布日期:2012-01-04
作者简介:敬明（1986- ），男，安徽合肥人，博士生.
基金资助:
国家自然科学基金（50908051）.

Indegree Statistics Shortest Path Algorithm Based on Probabilistic Search Delimitation

JING Ming, DENG Wei

Transportation College, Southeast University, Nanjing 210096, China

Received:2011-08-05 Revised:2011-09-19 Online:2011-12-25 Published:2012-01-04

摘要/Abstract

摘要： Dijkstra 经典最短路径算法包括大量的排序运算，且需要对图中所有顶点进行计算，效率较低.本文针对有向网络，提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径，依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值；采用入度统计算法代替经典的标号算法，在计算过程中根据节点阻抗最大值，采取一定方式剔除无效顶点(不在最短路径内的顶点)，简化网络结构.本文提出的算法不需要进行排序运算，简化了运算过程，并且可以剔除大量的无效顶点，降低了网络复杂度.算例分析表明，相对于Dijkstra算法，结合概率搜索定界的入度统计算法大幅度提高了运算效率，具有实用性.

关键词: 交通工程, 最短路算法, 入度统计, 概率搜索, 无效顶点

Abstract: The classical Dijkstra shortest path algorithm which needs both lots of sorting operation and calculation of all points in the network is comparatively low efficient. In this paper, an indegree statistics shortest path algorithm based on probabilistic search delimitation is proposed for calculation of directed network. The algorithm adopts probabilistic search to obtain a relatively short path, and defines a resistance maximum related to label numbers of points according to the length of the path. It replaces traditional labeling calculation by indegree statistics calculation, and eliminates invalid points (points that are not included in the shortest path) in the network according to resistance maximum of points. The proposed algorithm does not include sorting operation, and simplifies the network by eliminating invalid points. A numerical example shows its advantages compared with the Dijkstra algorithm, the proposed algorithm improves the computational efficiency and has practical value.

Key words: traffic engineering, shortest path algorithm, indegree statistics, probabilistic search, invalid point

中图分类号:

U491.2

敬明, 邓卫. 结合概率搜索定界的入度统计最短路径算法[J]. 交通运输系统工程与信息, 2011, 11(6): 169-174.

JING Ming, DENG Wei. Indegree Statistics Shortest Path Algorithm Based on Probabilistic Search Delimitation[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(6): 169-174.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18306.shtml

http://www.tseit.org.cn/CN/Y2011/V11/I6/169

参考文献

[1] 任凯, 浦金云. 有向赋权网络中任意节点对的最短路径集求解方法[J]. 计算机应用, 2010, 30:71-73.[REN K，PU J Y. Finding shortest paths between nodes in directed and weighted networks[J]. Journal of Computer Applications, 2010,30:71-73.]
[2] Tsitsiashvili G SH, Losev A S. Application of the Floyd algorithm to the asymptotic analysis of networks with unreliable ribs[J].Automation and Remote Control, 2008, 69(7)：1262-1265.
[3] Cherkassky B V, Goldberg A V,Radzik T.Shortest paths algorithms：theory and experimental evaluation[J]. Mathematical Programming, 1996, 73: 129-174.
[4] 王海梅, 周献中. 一种限制搜索区域的最短路径改进算法[J]. 南京理工大学学报，2009,33(5):638-642.[WANG H M，ZHOU X Z. Improved shortest path algorithm for restricted searching area[J]. Journal of Nanjing University of Science and Technology, 2009,33(5):638-642.]
[5] XUA M H，LIU Y Q. An improved Dijkstra’s shortest path algorithm for sparse network [J].Applied Mathematics and Computation,2007,185: 247-254.
[6] 郭云开, 雷敏, 李霞. 一种改进的路网最短路径算法[J]. 公路与汽运, 2007,4:32-34. [GUO Y K, LEI M, LI X. A improved shortest path algorithm[J].High ways & Automotive Applications,2007,4:32-34.]
[7] 李引珍, 郭耀煌.网络最短路径定界搜索算法[J].西南交通大学学报, 2004,39(5):561-564.[LI Y Z, GUO Y H. Bound searching algorithm for shortest path in a network [J]. Journal of Southwest Jiao Tong University, 2004,39(5):561-564.]
[8] 王卫强. 求图中受顶点数限制的所有最短路径的算法分析研究[D]. 上海：华东师范大学软件学院,2007.[WANG W Q. Verticesconstrained shortest path algorithms for networks[D]. East China Normal University,2007.]
[9] 徐风生, 李天志.所有最短路径的求解算法[J].计算机工程与科学, 2006, 28(12)：83-84. [XU F S, LI T Z. A new algorithm for finding all the shortest paths[J]. Computer Engineering & Science, 2006, 28(12)：83-84.]
[10] Azaron, A. . Bicriteria shortest path in networks of queues[J]. Applied Mathematics and Computation, 2006, 182(1)：434-442.
[11] Garcia N M，Lenkiewic　Z P, Freire M M，et al. On the performance of shortest path routing algorithms for modeling and simulation of static source routed networksAn extension to the Dijkstra algorithm[C]. 2nd International Conference on Systems and Networks Communications, ICSNC 2007，Cap Esterel, France,2007.

[1]	林建新, 刘博, 赵霞, 张蕾. 基于混合约束自编码器的机动车工况智能构建方法[J]. 交通运输系统工程与信息, 2022, 22(2): 109-116.
[2]	戢晓峰, 耿昭师. 山区双车道公路货车碰撞预测的双变量冲突极值模型[J]. 交通运输系统工程与信息, 2022, 22(2): 230-238.
[3]	张建波, 孙建平, 徐春玲, 郭镜霞, 温慧敏, 宋国华. 考虑交通运行条件影响的驾驶员特征聚类[J]. 交通运输系统工程与信息, 2022, 22(2): 330-336.
[4]	马景峰, 任刚, 李豪杰, 曹奇, 杜建玮. 电动自行车与机动车事故严重性影响因素分析[J]. 交通运输系统工程与信息, 2022, 22(2): 337-348.
[5]	宗芳, 王猛, 贺正冰. 考虑多车影响的分子动力学智能网联跟驰模型[J]. 交通运输系统工程与信息, 2022, 22(1): 37-48.
[6]	马小龙, 余强, 刘建蓓. 基于路侧毫米波雷达的车辆碰撞概率计算方法[J]. 交通运输系统工程与信息, 2022, 22(1): 57-66.
[7]	廖鹏, 唐铁桥. 基于车辆动力传动和转向系统的换道轨迹优化策略[J]. 交通运输系统工程与信息, 2022, 22(1): 98-105.
[8]	刘永红, 罗霞, 胡剑鹏. 考虑临时和预约需求的共享泊位动态分配方法[J]. 交通运输系统工程与信息, 2022, 22(1): 171-181.
[9]	袁振洲, 郭曼泽, 彭泳鑫, 杨洋. 基于梯度关联规则的老年行人交通事故风险识别[J]. 交通运输系统工程与信息, 2022, 22(1): 195-208.
[10]	张玉婷, 陈波佑, 张双焱, 闫学东, 李晓梦. 抵近信控交叉口分心驾驶识别模型[J]. 交通运输系统工程与信息, 2022, 22(1): 217-224.
[11]	宋浪, 王健, 杨滨毓, 安实. 连续流交叉口左转非机动车交通组织创新设计[J]. 交通运输系统工程与信息, 2022, 22(1): 225-233.
[12]	白婧荣, 唐伯明, 孙宗元, 毕辉云, 向恬君. 毗邻互通立交特长隧道驾驶负荷研究[J]. 交通运输系统工程与信息, 2022, 22(1): 301-310.
[13]	郭彦茹, 罗志雄, 王家川, 何方. 数据驱动的共享单车停放区规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(6): 9-16.
[14]	李君羡, 沈宙彪, 童文聪, 吴志周. 基于分类车头时距的城市道路大型车影响分析[J]. 交通运输系统工程与信息, 2021, 21(6): 55-62.
[15]	卢凯, 周志洁, 张勇刚, 赵世杰, 徐广辉. 面向单向交通路网的绿波协调设计方法[J]. 交通运输系统工程与信息, 2021, 21(6): 74-83.