A Contribution of Shortest Paths Algorithms to the NetworkX Python Library
Applied Sciences · 25.07.2025 · 15 (15) · 8273
DOI: 10.3390/app15158273 ↗Kurz gefasst
Fachartikel in der Zeitschrift Applied Sciences, online erschienen am 25.07.2025. Verfasst von Miguel Cruz und 9 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 78 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Funds through the Portuguese funding agency, FCT—Fundação para a Ciência e a Tecnologia.
Abstract (Originalsprache)
NetworkX is a free Python library for graphs and networks and is used in many applications and projects to find the shortest path in path planning scenarios. For dense graphs, the library provides the Floyd–Warshall algorithm for shortest paths and the A* (“A-Star”) algorithm for shortest paths and path lengths. However, several extensions have been proposed to improve the A*, but they are not included in the library. In this context, this paper presents a set of implementations improving the A*, such as the IDA*, D* Lite, SMA*, Bidirectional A* and RTA*. The goal or challenge is to address the limitations of the A* in specific scenarios, such as searching for an optimal path repeatedly or when confronted with memory limitations, as exemplified by the NetworkX library. To do this, we first review the literature of the usage and general application of NetworkX in different domains of applicability and then explore their usage in a shortest path context. By reviewing and validating the usage of A* and extensions in Python using the NetworkX framework, the implementations were submitted to the network environment validation and passed the tests. We have also done the benchmarking of the A*, comparing it with the new ones, and concluded the better efficiency of the A* extensions in tri-objective scenario parameters (length, cost and toll). Despite the extensive utilisation of A* and its notable efficacy in identifying optimal paths, its performance is suboptimal in specific scenarios, such as when confronted with memory constraints and dynamic environments. Almost every algorithm outperformed or matched the A* in the fields that were developed to have an advantage, demonstrating the quality and robustness of the implemented algorithms. As a contribution and to foster further research in this shortest path specific context field, the dataset and Python code of the algorithms are available in a GitHub opensource repository.
Förderung
- National Funds through the Portuguese funding agency, FCT—Fundação para a Ciência e a Tecnologia
Zitieren
APA
Cruz, M., Carvalho, R., Costa, A., Pinto, L., Dias, L., Cerqueira, P., Machado, R., Batista, T., Castro, P., & Ribeiro, J. (2025). A Contribution of Shortest Paths Algorithms to the NetworkX Python Library. Applied Sciences, 15(15), 8273. https://doi.org/10.3390/app15158273
Vancouver
Cruz M, Carvalho R, Costa A, Pinto L, Dias L, Cerqueira P, et al. A Contribution of Shortest Paths Algorithms to the NetworkX Python Library. Applied Sciences. 2025;15(15):8273. doi:10.3390/app15158273
BibTeX
@article{Cruz2025,
author = {Cruz, Miguel and Carvalho, Rui and Costa, André and Pinto, Luis and Dias, Luis and Cerqueira, Paulino and Machado, Rodrigo and Batista, Tiago and Castro, Pedro and Ribeiro, Jorge},
title = {A Contribution of Shortest Paths Algorithms to the NetworkX Python Library},
journal = {Applied Sciences},
year = {2025},
volume = {15},
number = {15},
pages = {8273},
doi = {10.3390/app15158273}
}
EUVIMED