The thesis addresses a comparison of algorithms for finding the shortest (cheapest) path in a graph. The work presents a comparison of the theoretical time complexity of the algorithms and their performance in practical implementation.
The thesis is divided into four thematic sections. First, we provided an overview of the five algorithms under consideration — Dijkstra’s algorithm with a binary heap, Dijkstra’s algorithm with a Fibonacci heap, the Bellman–Ford algorithm, Johnson’s algorithm, and the Floyd–Warshall algorithm — along with a description of how they work and their theoretical time complexity. In the second section, we described the test datasets, which are divided into artificially generated graphs and standard graphs from the SNAP dataset collection, representing real-world networks. The third section describes the ALGator testing environment, in which all experiments were carried out. The fourth section presents an overview and comparison of the test results, along with a discussion of the findings.
In analyzing the results, we placed emphasis on identifying deviations from theoretically expected values and explaining them. We highlighted two main deviations. The first concerns the behavior of Dijkstra’s algorithm: the implementation with a binary heap proves to be faster in practice than the implementation with a Fibonacci heap, even though the latter has better theoretical time complexity. The reason lies in the higher constant factors and poorer cache locality of the Fibonacci heap. The second deviation was observed in graphs with more than one million vertices and an exceptionally low density, where Johnson’s algorithm outperforms Bellman–Ford, despite the latter having better asymptotic complexity.
|
