GRAPH SHORTEST PATH ALGORITHMS AND THEIR APPLICATIONS

Hristo Hristov, Student

Department of Informatics and Information Technologies University of Ruse “Angel Kanchev”

E-mail: s236266@stud.uni-ruse.bg

Assoc. Prof. Galina Atanasova, PhD

Department of Informatics and Information Technologies University of Ruse “Angel Kanchev”

E-mail: gatanasova@uni-ruse.bg

Abstract

This paper provides a review of shortest-path algorithms across several categories: single source shortest path, all-pairs shortest path, and heuristic algorithms. We review both classical algorithms and recently developed approaches, analyzing and comparing them to one another to determine their practical applications and efficiency in terms of computational complexity and memory usage. This paper aims to provide insights into the trade-offs among these algorithms while summarizing recent developments in the field of graph theory.

Keywords

Graph, Shortest Path Algorithms, Trade-Offs, Optimizations, Recent Developments

REFERENCES

Taheri-Dehkordi, M. (2024). Graph Theory; History, Applications and Vision. Journal of Mathematics and Society. ResearchGate
Roughgarden, T. (2018). Algorithms Illuminated: Graph algorithms and data structures. Part 2. Soundlikeyourself Publishing LCC.
Robinson, S. (2023, February 17). What is Graph Data Science? A complete introduction to critical new ways of analyzing your data. Graphable AI. https://www.graphable.ai/blog/graph-data-science/
Erdos, P., Rényi, A. (1960). On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1), 17-60.
Ahuja, R., Mehlhorn, K., Orlin, J. and Tarjan, R. 1990. Faster algorithms for the shortest path problem. J. ACM 37, 2 (April 1990), 213-223. https://doi.org/10.1145/77600.77615
Bernstein, A., Nanongkai, D., Wulff-Nilsen, C. (2023). Negative-weight single-source shortest paths in near-linear time. arXiv preprint arXiv:2203.03456. https://arxiv.org/abs/2203.03456
Johnson, D. (1977). Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM 24, 1 (Jan. 1977), 1-13. https://doi.org/10.1145/321992.321993
Zou, X. (2013). An Improved SPFA Algorithm for Single-Source Shortest Path Problem Using Forward Star Data Structure.
Las Vegas algorithm. (n.d.). Wikipedia. Retrieved May 1, 2025, from https://en.wikipedia.org/wiki/Las_Vegas_algorithm
Nakov, P., Dobrinkov, P. (2015). Programming=++Algorithms; (5th edition). Software University
Rubio, F. (2023, June 6). Pathfinding Algorithms- Top 5 Most Powerful. Graphable. Retrieved May 1, 2025, from https://www.graphable.ai/blog/pathfinding-algorithms/