Dijkstra’s Shortest Path Algorithm and Its Application on Bus Routing
- https://doi.org/10.2991/aebmr.k.220502.058How to use a DOI?
- Computer Science; Shortest Path; Dijkstra’s Algorithm; Bus Routing; Algorithm
The shortest path problem is common in computer science and has wide application in life. The shortest path algorithm is designed to solve these problems and the most classic and useful one is Dijkstra’s shortest path algorithm which Dijkstra introduced in 1959. This paper presents and analyzes normal shortest path problems starting from the explanation of graphs and how they are divided into their practical examples. Common shortest path algorithms are also explained including their basic mechanism. Focusing on Dijkstra’s algorithm, the paper analyzes its specific process and mechanism in a detailed way. Plus, the paper also analyzes the possibility of usage of Dijkstra’ algorithm on public transit and roads. Considering the characteristic of bus transportation in Walnut, the paper concluded that Dijkstra’s Algorithm can be used on Walnut bus transportation and set up a list of preconditions for the system to succeed. Based on the above work, a bus query system is implemented for the City of Walnut. “Walnut Bus Transportation Query System” serves as a reference to help residents choose the shortest road from the starting bus station to the ending bus station, thus saving time for the user.
- © 2022 The Authors. Published by Atlantis Press International B.V.
- Open Access
- This is an open access article distributed under the CC BY-NC 4.0 license.
Cite this article
TY - CONF AU - Ruiting Chen PY - 2022 DA - 2022/05/16 TI - Dijkstra’s Shortest Path Algorithm and Its Application on Bus Routing BT - Proceedings of the 2022 International Conference on Urban Planning and Regional Economy（UPRE 2022） PB - Atlantis Press SP - 321 EP - 325 SN - 2352-5428 UR - https://doi.org/10.2991/aebmr.k.220502.058 DO - https://doi.org/10.2991/aebmr.k.220502.058 ID - Chen2022 ER -