Proceedings of the 2016 International Conference on Civil, Transportation and Environment

A New Implementation of Dijkstra’s Algorithm on Urban Rail Transit Network

Authors
Jimeng Tang, Quanxin Sun, Zhijie Chen
Corresponding Author
Jimeng Tang
Available Online January 2016.
DOI
10.2991/iccte-16.2016.85How to use a DOI?
Keywords
shortest paths; improved Dijkstra’s algorithm; urban rail transit network; nodes with weights; labeling edge.
Abstract

Paths searching is a significant work for urban rail transit network. Because of various time weights included in nodes on this network, the traditional Dijkstra’s algorithm fails to find the shortest paths. In order to still use this traditional algorithm, the general approach is to expand this network, but additional efforts are introduced. Another approach that will be proposed in this paper adopt the dual principle which changes the label-object from node to edge, and it doesn’t need to expand the network, meanwhile, we take the time into/outside a station into account. The improved Dijkstra’s algorithm has a time complexity of O(mlogm). And the comparison of their computational efficiency on urban rail transit of Beijing shows that the new algorithm’s computing time is a little longer than the traditional algorithm’s. The time difference is about 0.016 seconds between a single OD pairs averagely. However, we think that the saving time with no need for additional efforts can balance the increased computing time.

Copyright
© 2016, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2016 International Conference on Civil, Transportation and Environment
Series
Advances in Engineering Research
Publication Date
January 2016
ISBN
978-94-6252-185-8
ISSN
2352-5401
DOI
10.2991/iccte-16.2016.85How to use a DOI?
Copyright
© 2016, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Jimeng Tang
AU  - Quanxin Sun
AU  - Zhijie Chen
PY  - 2016/01
DA  - 2016/01
TI  - A New Implementation of Dijkstra’s Algorithm on Urban Rail Transit Network
BT  - Proceedings of the 2016 International Conference on Civil, Transportation and Environment
PB  - Atlantis Press
SP  - 507
EP  - 513
SN  - 2352-5401
UR  - https://doi.org/10.2991/iccte-16.2016.85
DO  - 10.2991/iccte-16.2016.85
ID  - Tang2016/01
ER  -