# A Contribution of Shortest Paths Algorithms to the NetworkX Python Library
## 3 Foundations
### Iterative-Deepening-A*(IDA*)  
In order to reduce the memory requirements of the A* algorithm, [PERSON] (1985) [31] presented Iterative-Deepening-A* (IDA*), observing that A* stores all the nodes it generates in the open or closed lists, and hence is severely space-limited in practice. In contrast, IDA* requires space that is only linear in the maximum search depth, and it is often faster than A* because it incurs less overhead per node. IDA* combines features of iterative deepening depth-first search and is also referred to as a memory-efficient version of A*, as it requires significantly less memory while still ensuring optimal pathfinding. In this sense, by following a depth-first search, IDA* does not store most previously generated nodes. The main overhead of IDA* is not the initial iterations but rather from re-expansions during the same iteration of the same states via different paths, called duplicate nodes, in graphs with cycles. In other words, the main difference between IDA* and standard iterative deepening is that the cutoff used is the _f-cost_ (\(g+h\)) rather than the depth. At each iteration, the cutoff value is the smallest _f-cost_ of any node that exceeded the cutoff on the previous iteration [32]. The IDA* uses a heuristic function called F-score, which is used to estimate the cost of reaching the goal state from a given state, which is a combination of two other heuristic functions, \(g(n)\) and \(h(n)\). It is used to determine the order in which the algorithm expands nodes in the search tree, and thus it plays an important role in how quickly the algorithm finds a solution. A lower F-score indicates that a node is closer to the goal state and will be expanded before a node with a higher F-score. The general process of the IDA* can be described as follows in Algorithm 2:  
```
1 Variables:
2 path:current search path
3 node:current node (last node in current path)
4g:the cost to reach current node
5 festinated cost of the cheapest path
6h(node):estimated cost of the cheapest path
7 cost(node, succ):step cost function
8 is_goal(node):goal
9 success(node):expand nodes ordered by g + h(node)
10 ida_star(root):return a pair with the best path and its cost
11 procedureida_star(root)
12 bound = h(root)
13 path = [root]
14 path = [root]
15 loop
16 lct = search(path, 0, bound)
17 ift = FOUNDthen
18 return (path, bound)
19 ift = [then
20 return NOT_FOUND
21 bound = t
```  
**Algorithm 2** IDA* algorithm pseudocode [31].  
IDA* was the first widely used optimal, memory-bounded heuristic search algorithm, and many variants have since been developed. [PERSON] (1995) [72] explored the Bidirectional perimeter search algorithm, known as BIDA*. [PERSON] and [PERSON]. (2019) [59] presented a simple hybrid search algorithm with the combination of A* and IDA*. The main goal is to run A* until memory is almost exhausted, then execute IDA* starting from the frontier nodes, which are the nodes open at the end of the A* phase.  
Regarding this algorithm, it is important to mention that the original version of the implementation is presented in a recursive form. However, the same algorithm can be implemented with the same characteristics and functionalities in a non-recursive form. In this project, we started by following the recursive approach using the Python programming language. However, there was a limitation in the processing of Python scripts with a limit of 1000 iterations that blocked the execution when this value was exceeded. To overcome this limitation, we implemented the IDA* algorithm with the same objectives and functionalities, but without implementing the recursive form.