A comparison of Dijkstra's Algorithm using fibonacci heaps, binary heaps, and self-balancing binary trees

Lewis, Rhydian ORCID: https://orcid.org/0000-0003-1046-811X 2023. A comparison of Dijkstra's Algorithm using fibonacci heaps, binary heaps, and self-balancing binary trees. [Online]. Preprint repository: ArXiv. Available at: https://arxiv.org/abs/2303.10034

Preview

PDF - Submitted Pre-Print Version Download (1MB) | Preview

Abstract

This paper describes the shortest path problem in weighted graphs and examines the differences in efficiency that occur when using Dijkstra's algorithm with a Fibonacci heap, binary heap, and self-balancing binary tree. Using C++ implementations of these algorithm variants, we find that the fastest method is not always the one that has the lowest asymptotic complexity. Reasons for this are discussed and backed with empirical evidence.

Item Type:	Website Content
Status:	Unpublished
Schools:	Mathematics
Publisher:	ArXiv
Date of First Compliant Deposit:	22 March 2023
Date of Acceptance:	22 March 2023
Last Modified:	24 Mar 2023 15:00
URI:	https://orca.cardiff.ac.uk/id/eprint/157867

Actions (repository staff only)

Edit Item