Theoretical Time Complexity of Dijkstra’s Algorithm Variants: A Review
Download| Volume 5 Issue 1 2024 | |
|---|---|
| Author(s): |
Khalid Nooruddin Charan Hamdard University, Karachi, Pakistan, khalid.chaaran@hamdard.edu.pk Shahid Munir Shah Hamdard University, Karachi, Pakistan, shahid.munir@hamdard.edu.pk Lachhman Das Dhomeja University of Sindh, Jamshoro, Pakistan, lachhman@usindh.edu.pk Shahzad Ahmed Memon School of Architecture, Computing and Engineering, University of East London, UK, s.memon@uel.ac.uk Nisar Ahmed Memon University of Sindh, Jamshoro, Pakistan, nisar.memon@usindh.edu.pk Mahmood Aljawarneh Applied Science Private University Amman, Jordan, ma_aljawrneh@asu.edu.jo |
| Abstract | Complex networks formed by people, cities, computers, genes, and financial transactions, etc. as nodes and their interdependent associations as links exist in real world. Often, multiple links connect two nodes in these networks. It is essential in many applications to discover shortest path between the nodes. Shortest path problems are computation resources intensive particularly the computational time, therefore, the shortest path algorithms are analyzed to predict their computational time complexity. Plethora of literature presents comparative studies of shortest path algorithms; however, the compared algorithms provide the solutions to dissimilar settings of input network graphs. State-of-the-art Dijkstra’s algorithm efficiently solves single source shortest path problem for non-negative weighted directed graphs. The algorithm selects a node with minimum distance from start node and traverse input graph. Different techniques used to implement queue resulted in different time complexity of variants of Dijkstra’s algorithm. The scope of our work is to analyze time complexity of the classical Dijkstra’s algorithm variants and highlight the bottlenecks that set computational upper bound of their time complexities. The outcome of this article is to recap time complexity improvements of the Dijkstra’s algorithm introduced by various advancements in the data structures. This may assist the research to provide some more efficient solution for single source shortest path problems. |
| Keywords | Graph theory; shortest path; time complexity; heap data structures; Dijkstra’s algorithm. |
| Year | 2024 |
| Volume | 5 |
| Issue | 1 |
| Type | Research paper, manuscript, article |
| Recognized by | Higher Education Commission of Pakistan, HEC | Category | Journal Name | ILMA Journal of Technology & Software Management | Publisher Name | ILMA University | Jel Classification | -- | DOI | - | ISSN no (E, Electronic) | 2790-590X | ISSN no (P, Print) | 2709-2240 | Country | Pakistan | City | Karachi | Institution Type | University | Journal Type | Open Access | Manuscript Processing | Blind Peer Reviewed | Format | Paper Link | https://ijtsm.ilmauniversity.edu.pk/arc/Vol5/i1/pdf5.pdf | Page | 37-41 |