Vol. 2 No. 1 (2022)
Articles

A Computationally Reproducible Approach to Dijkstra’s Shortest Path Algorithm

PDF
  • Berk Anbaroğlu,
  • Muammer Özkan,
  • Ayça Tabakoğlu,
  • Ekin Gönenç Uygun
Berk Anbaroğlu
Hacettepe University

Published 2022-03-30

Keywords

  • Shortest path,
  • Routing Algorithms,
  • Dijkstra’s Algorithm,
  • NetworkX

How to Cite

Anbaroğlu, B., Özkan, M., Tabakoğlu, A. ., & Uygun, E. G. (2022). A Computationally Reproducible Approach to Dijkstra’s Shortest Path Algorithm. Advanced Geomatics, 2(1), 01–06. Retrieved from https://publish.mersin.edu.tr/index.php/geomatics/article/view/161

Copyright (c) 2022 Advanced Geomatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Abstract

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.

PDF

References

  1. ACM SIGSPATIAL GIS Cup 2015. (n.d.). Retrieved from https://research.csc.ncsu.edu/stac/GISCUP2015/index.php
  2. 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
  3. 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
  4. Ç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
  5. GitHub—Banbar/shortest_path_Dijkstra. (n.d.). Retrieved from https://github.com/banbar/shortest_path_Dijkstra
  6. 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
  7. 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
  8. 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
  9. Necaise, R. D. (2011). Data structures and algorithms using Python. Hoboken, N.J: Wiley.
  10. Overview—NetworkX 1.10 documentation. (n.d.). Retrieved February 10, 2022, from https://networkx.org/documentation/networkx-1.10/overview.html
  11. 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
  12. 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
  13. 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