# A Contribution of Shortest Paths Algorithms to the NetworkX Python Library
## 5 Experiments and Results
### Analysis and Discussion  
Following the foundations, context and dataset described in previous sections, we conducted a benchmarking of the A* algorithm in comparison with five newly implemented algorithms in the NetworkX library, within tri-objective scenario parameters (distance, cost and toll). After the various simulations using the different algorithms, we observed that some algorithms have advantages over others depending on the metrics. For example, and according to the graphs and metrics shown in the previous section, with regards to determining the optimal path between an origin and a destination (between Tirana and Helsinki cities), we achieved the following results in terms of algorithm performance, summarised in Table 1.  
From the table and simulation results, and considering the overall metrics of each algorithm, it is noticeable that the A* algorithm and the SMA* algorithm demonstrated a good overall performance, although SMA* showed an overall good performance, demonstrating competitive results in comparison to all the other implemented algorithms. Nevertheless, almost all other algorithms were able to perform equally well, in particular in the metrics related to the characteristics where they were specifically developed to have an advantage, highlighting the implementation quality and robustness of the implemented algorithms. Regarding the D* Lite and RTAA* algorithms that were developed for handling larger graphs and faster recalculation times on path changes during execution, these algorithms are more complex than the rest of the variants. Considering the small size of the test graph and the absence of path changes during executions, these algorithms were not able to fully \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Algorithm** & **Time** & **Total Cost** & **Peak Memory** & **Avg. Memory** & **Recalculation** & **Bulk Average** \\  & & & & & **Time** & **Time** \\ \hline A* & 0.16 ms 1 & 2678 & 2.88 Kb 2 & 2.86 Kb 2 & 0.04 ms 1 & 0.04 ms 1 \\ D* Lite & 1.01 ms 1 & 2678 & 77.26 Kb 2 & 76.99 Kb 2 & 0.58 ms 1 & 0.06 ms 1 \\ Bidirectional A* & 0.17 ms 1 & 2790 & 8.44 Kb 2 & 8.44 Kb 2 & 0.06 ms 1 & 0.06 ms 1 \\ IDA* & 14.13 ms 1 & 2678 & 2.64 Kb 2 & 2.59 Kb 2 & 12.56 ms 1 & 3.48 ms 1 \\ RTAA* & 0.22 ms 1 & 3485 & 6.58 Kb 2 & 6.58 Kb 2 & 0.11 ms 1 & 0.09 ms 1 \\ SMA* & 0.08 ms 1 & 2678 & 2.57 Kb 2 & 2.57 Kb 2 & 0.06 ms 1 & 0.05 ms 1 \\ \hline \end{tabular}  
* Time units converted from seconds to milliseconds for better visualization. 2 Memory units converted from Megabits to Kilobits for better visualization.  
\end{table} 
Table 1: Comparison between the algorithms’ performances. Figure 8: Optimal path found between Tirana and Helsinki by the Simplified Memory Bounded A* algorithm (red line) in comparison to the benchmark of the A* algorithm. leverage their advantages, thus justifying the worse results in certain fields when compared to the A* algorithm benchmark. The IDA* algorithm is designed to enhance memory utilisation through the implementation of a depth-first search strategy and is relevant in scenarios where a graph contains numerous branches, potentially resulting in devices with insufficient memory to accommodate all branches. The D*-Lite algorithm has been developed to address the limitations of the A* algorithm when searching for a given path that involves the reuse of parts of a previous path and is relevant in the context of large graphs, where the D*-Lite algorithm has been shown to enhance performance. The SMA* algorithm imposes a limit on the amount of memory that can be utilised, which renders it particularly advantageous for devices with limited memory resources. Bidirectional A* aims to reduce the time taken to search for a given path by searching in both directions, whereas A* only searches from the source. The RTAA* aims to determine a given path faster than A*, and although it is not the optimal solution it returns a result according to certain limits imposed by its parameters, such as the search depth of a given node.