# A Contribution of Shortest Paths Algorithms to the NetworkX Python Library
## 2 Literature Review  
Based on free and opensource tools, several tools have been presented over the last few decades for graph visualization as well as for representing scenarios of shortest path problems. With promising results, the NetworkX library, created by [PERSON], [PERSON] and [PERSON] [16], has been explored and improved, especially for network analysis and visualization, as well as for shortest path problems using classic algorithms, as compiled and published in research papers and in published books [34; 35; 36]. Analysing the literature review of the usage and exploration of NetworkX, the main use is centred on network analysis, such as the works of [PERSON] et al. (2012) [37], [PERSON] (2015) [38], [PERSON] et al. (2018) [39], [PERSON] et al. (2019) [40], [PERSON], [PERSON] (2020) [17], [PERSON] et al. (2021) [18], [PERSON] et al. (2022) [19] and [PERSON] et al. (2023) [20]. However, besides the main usage and exploration in graph and network analysis as well as in visualization, NetworkX has also been applied and explored in shortest path problems, particularly in both undirected and directed graphs with weighted and unweighted constraints between nodes in the graphs, as well as in scenarios involving dense graphs. In the context of path search, path planning or route planning, there are several well-known algorithms. [PERSON]'s algorithm [22; 41] is a method used to find the shortest path from one node to another in a graph that only has positive weights. In 1968, [PERSON] et al. (1968) [29] presented a study that, with a formal basis for the heuristic determination of minimum cost paths, introduced the A* algorithm. The main difference between [PERSON]'s algorithm and A* is the use of a heuristic estimate function. This function estimates, for any node, the remaining distance to the destination. [PERSON] may be regarded as an instance of A* where the heuristic estimate function is identically zero (function \(\equiv\) 0) [30]. However, as A* has shown limitations when applied to more complex problems, improved variants have emerged to achieve faster registration results and increase efficiency. Consequently, several studies and extensions have been presented [21; 31; 32; 41; 42; 43; 44], particularly in terms of performance time and memory usage. [PERSON] (1985) [31] and [PERSON] (1989) [45] are two examples of those who started the research of analysing the memory constraints in heuristic search. Iterative Deepening A-Star (IDA*) was presented by [PERSON] in 1985 and addresses the memory problem by combining depth first search with incrementally increasing f-cost limits and allowing for an optimal search without the need to maintain every node in the memory. Other studies have followed this limitation. Simplified Memory-bounded A* (SMA*) [32; 46] is a shortest path algorithm that is based on the A* algorithm. The difference between SMA* and A* is that SMA* uses a bounded memory, while A* might need exponential memory. Dynamic A* (D*) [33; 34] tries to deal with dynamic obstacles by updating edge weights in real time. D* maintains a list of nodes used to propagate information about changes of the cost function during the search of the path. D* Lite [33] implements the same behaviour of D* using an incremental heuristic search algorithm, i.e., it incrementally repairs solution paths when changes occur, promoting fast replanning. Anytime Repairing A* (ARA*) [47; 48], by using a flexible time cost, returns a valid solution to a search path problem, even if it is interrupted before it ends, generating a non-optimal solution before progressively optimizing the solution for the search problem. Lifelong Planning A* (LPA*) [49; 50] adapts the search process to changes in the graph without the need for recomputation. It updates the distance-from-start estimates calculated in the previous search during the current search, correcting only those that have become inconsistent in order to maintain shortest-path optimality.