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

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)

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  -