Comparative Study Of Various Approaches Of Dijkstra Algorithm
Divyam Verma, Devansh Messon, Mayank Rastogi, Amit Singh
20212021 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS)32 citationsDOI
Abstract
Dijkstra algorithm is not improved in terms of space and time-complexity, the algorithm is muddled to apply in network analysis for enormous test cases. To handle this huge time complexity, advanced structures are applied to enhance Dijkstra algorithm. The use of a keen and numerical procedure speeds up the enhanced Dijkstra by multiple times. In this paper four approaches using advanced data structures like linked list, Fibonacci heap, binary heap and bi-directional Dijkstra are applied and their performance is also analyzed and compared on two classes of graphs, dense and sparse graphs.
Topics & Concepts
Dijkstra's algorithmHeap (data structure)Computer scienceAlgorithmA* search algorithmFloyd–Warshall algorithmData structureTheoretical computer scienceGraphShortest path problemProgramming languageSoftware Testing and Debugging TechniquesData Management and AlgorithmsSoftware System Performance and Reliability