Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline
Computers · 10.12.2025 · 14 (12) · 545
DOI: 10.3390/computers14120545 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computers, online erschienen am 10.12.2025. Verfasst von Nahier Aldhafferi. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This study presents a comparative evaluation of Dijkstra’s algorithm, A*, Bellman-Ford, AI-Augmented A* and a neural AI-based model for shortest-path computation across diverse graph topologies, with a focus on time efficiency and memory consumption under standardized experimental conditions. We analyzed grids, random graphs, and scale-free graphs of sizes up to 103,103 nodes, specifically examining 100- and 1000-node grids, 100- and 1000-node random graphs, and 100-node scale-free graphs. The algorithms were benchmarked through repeated runs per condition on a server-class system equipped with an Intel Xeon Gold 6248R processor, NVIDIA Tesla V100 GPU (32 GB), 256 GB RAM, and Ubuntu 20.04. A* consistently outperformed Dijkstra’s algorithm when paired with an informative admissible heuristic, exhibiting faster runtimes by approximately 1.37× to 1.91× across various topologies. In comparison, Bellman-Ford was slower than Dijkstra’s by approximately 1.50× to 1.92×, depending on graph type and size; however, it remained a robust option in scenarios involving negative edge weights or when early-termination conditions reduced practical iterations. The AI model demonstrated the slowest performance across conditions, incurring runtimes that were 2.60× to 3.23× higher than A* and 1.62× to 2.15× higher than Bellman-Ford, offering limited gains as a direct solver. These findings underscore topology-sensitive trade-offs: A* is preferred when a suitable heuristic is available; Dijkstra’s serves as a strong baseline in the absence of heuristics; Bellman-Ford is appropriate for handling negative weights; and current AI approaches are not yet competitive for exact shortest paths but may hold promise as learned heuristics to augment A*. We provide environmental details and comparative results to support reproducibility and facilitate further investigation into hybrid learned-classical strategies.
Zitieren
APA
Aldhafferi, N. (2025). Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline. Computers, 14(12), 545. https://doi.org/10.3390/computers14120545
Vancouver
Aldhafferi N. Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline. Computers. 2025;14(12):545. doi:10.3390/computers14120545
BibTeX
@article{Aldhafferi2025,
author = {Aldhafferi, Nahier},
title = {Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline},
journal = {Computers},
year = {2025},
volume = {14},
number = {12},
pages = {545},
doi = {10.3390/computers14120545}
}
EUVIMED