A contribution of shortest paths algorithms to the networkX python library

Abstract

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.