An Experimental Comparison of Implementations of Dijkstra’s Single Source Shortest Path Algorithm Using Different Priority Queues Data Structures
Andrei-Daniel Andreiana, Costin Bădică, Eugen Ganea · 2020
We compare multiple implementations of Dijkstra's single source shortest paths algorithm using two different data structures. The algorithms are implemented in Python programming language and the test data consisted of graphs with 1,000 vertices and up to 900,000 edges, split into sparse and dense graphs. These implementations have different theoretical time orders of complexity and the experiment aims to test if any of them is more suitable for certain types of graphs. The min-max binary heap implementation uses a min binary tree to keep the distances to the vertices. The distances to all vertices are held in an array, but their positions change, so extra logic is required to access them. The Fibonacci heap (FH) implementation uses a Fibonacci forest to keep the distances to the vertices. While implementing this data structure is more elaborate, it offers a good theoretical time order of complexity.