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/).
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 -