Dijkstra’s Shortest Path Algorithm and Its Application on Bus Routing

DOI

10.2991/aebmr.k.220502.058How to use a DOI?

Keywords

Computer Science; Shortest Path; Dijkstra’s Algorithm; Bus Routing; Algorithm

Abstract

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.

Copyright

© 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.

Download article (PDF)

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  - 10.2991/aebmr.k.220502.058
ID  - Chen2022
ER  -