A Computationally Reproducible Approach to Dijkstra’s Shortest Path Algorithm
Keywords:
Shortest path, Routing Algorithms, Dijkstra’s Algorithm, NetworkXAbstract
One of the common problems in spatial analysis is the Shortest Path Problem (SPP), which aims to determine the shortest path between any given two points on a network structure. Although Shortest Path Problem is a widely used in spatial analysis, there has been lack of online resources to ease learning of the method with a computationally reproducible approach. This article presents how Dijkstra's algorithm works when finding the shortest path. Specifically, the developed online tutorial relied on the openly available road network data of San Francisco, NetworkX a Python package to realize complex graph analysis, and finally QGIS to visualize the shortest paths. All of the discussed material is presented as a Jupyter Notebook to ease computational reproducibility.
References
ACM SIGSPATIAL GIS Cup 2015. (n.d.). Retrieved from https://research.csc.ncsu.edu/stac/GISCUP2015/index.php
Ahuja, R. K., Mehlhorn, K., Orlin, J. & Tarjan, R. E. (1990). Faster algorithms for the shortest path problem. Journal of the ACM, 37(2), 213–223. https://doi.org/10.1145/77600.77615
Anbaroğlu, B. (2021). A collaborative GIS programming course using GitHub Classroom. Transactions in GIS, 25(6), 3132–3158. https://doi.org/10.1111/tgis.12810
Çalışkan, M. & Anbaroğlu, B. (2020). Geo-MST: A geographical minimum spanning tree plugin for QGIS. SoftwareX, 12, 100553. https://doi.org/10.1016/j.softx.2020.100553
GitHub—Banbar/shortest_path_Dijkstra. (n.d.). Retrieved from https://github.com/banbar/shortest_path_Dijkstra
Huber, S. & Rust, C. (2016). Calculate Travel Time and Distance with Openstreetmap Data Using the Open Source Routing Machine (OSRM). The Stata Journal: Promoting Communications on Statistics and Stata, 16(2), 416–423. https://doi.org/10.1177/1536867X1601600209
Kim, B. & Henke, G. (2021). Easy-to-Use Cloud Computing for Teaching Data Science. Journal of Statistics and Data Science Education, 29(sup1), S103–S111. https://doi.org/10.1080/10691898.2020.1860726
Kumar, R., Kumar, S. & Soni, A. (2021). Election prediction using twitter and GIS. 2021 International Conference on Advance Computing and Innovative Technologies in Engineering (ICACITE), 306–311. https://doi.org/10.1109/ICACITE51222.2021.9404671
Necaise, R. D. (2011). Data structures and algorithms using Python. Hoboken, N.J: Wiley.
Overview—NetworkX 1.10 documentation. (n.d.). Retrieved February 10, 2022, from https://networkx.org/documentation/networkx-1.10/overview.html
Rout, R. R., Vemireddy, S., Raul, S. K. & Somayajulu, D. V. L. N. (2020). Fuzzy logic-based emergency vehicle routing: An IoT system development for smart city applications. Computers & Electrical Engineering, 88, 106839. https://doi.org/10.1016/j.compeleceng.2020.106839
Yu, L., Kong, D., Shao, X. & Yan, X. (2018). A Path Planning and Navigation Control System Design for Driverless Electric Bus. IEEE Access, 6, 53960–53975. https://doi.org/10.1109/ACCESS.2018.2868339
Zeng, W. & Church, R. L. (2009). Finding shortest paths on real road networks: The case for A*. International Journal of Geographical Information Science, 23(4), 531–543. https://doi.org/10.1080/13658810801949850
