| 引用本文: | 谢建平,陈治亚,邓连波,等.改进Dijkstra算法在大型城市轨道交通网计价系统中的应用.[J].国防科技大学学报,2021,43(1):109-116.[点击复制] |
| XIE Jianping,CHEN Zhiya,DENG Lianbo,et al.Application of improved Dijkstra algorithm in large urban rail transit network valuation system[J].Journal of National University of Defense Technology,2021,43(1):109-116[点击复制] |
|
| |
|
|
| 本文已被：浏览 7109次 下载 5554次 |
| 改进Dijkstra算法在大型城市轨道交通网计价系统中的应用 |
| 谢建平1,2,陈治亚1,邓连波1,谢宜斌2,杨坤2 |
|
(1. 中南大学 交通运输工程学院, 湖南 长沙 410075;2. 长沙市轨道交通集团有限公司, 湖南 长沙 410133)
|
| 摘要: |
| 随着城市地铁建设的迅猛发展,国内众多城市地铁线路均已实现网络化运营。考虑到地铁票价制定的公益性,目前国内大部分城市均以最短路径或最少车站的方式计算线网两车站间的票价。以传统的Dijkstra算法为基准,对传统的Dijkstra算法进行改进,分别采用传统Dijkstra算法和改进Dijkstra算法对长沙地铁1~5号线线网最短距离行走路线进行测算。结果表明,改进后的Dijkstra算法不仅有效地提高了算法的时效性,克服了传统算法时间冗长的缺陷,在一定程度上消除了线路之间累积的误差且提高了线网的可延展性。 |
| 关键词: 长沙地铁1~5号线 城市地铁票价 Dijkstra算法 最短路径算法 |
| DOI：10.11887/j.cn.202101015 |
| 投稿日期：2020-05-09 |
| 基金项目:国家自然科学基金资助项目(71471179) |
|
| Application of improved Dijkstra algorithm in large urban rail transit network valuation system |
| XIE Jianping1,2, CHEN Zhiya1, DENG Lianbo1, XIE Yibin2, YANG Kun2 |
|
(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China;2. Changsha Metro Group Co.,Ltd, Changsha 410133, China)
|
| Abstract: |
| With the rapid development of urban subway construction, many city subway lines have been networked.Considering the public welfare when making ticket price, most cities in China calculate the ticket price between the two stations of the line network by the shortest path or the least stations now. the traditional Dijkstra algorithm was improved based on the traditional Dijkstra algorithm. The traditional Dijkstra algorithm and the improved Dijkstra algorithm were respectively used to calculate the shortest walking route of Changsha metro line 1~5 network. Results show that the improved Dijkstra algorithm not only effectively improves the efficiency of the algorithm and overcomes the long-time defect of the traditional algorithm, but also partly eliminate the accumulated errors between lines and improve the ductility of the network. |
| Keywords: Changsha metro line 1~5 urban subway fare Dijkstra algorithm shortest path algorithm |
|
|
|
|
|
