# A Contribution of Shortest Paths Algorithms to the NetworkX Python Library
## 3 Foundations
### A-Star  
The A* or \"A-Star\" ([PERSON], 1968) [29], a variant of the Dijkstra ([PERSON], 1959) [22], is a well know algorithm [32; 42; 43]. It evaluates nodes by combining \(g(n)\), the cost reach node (or actual cost), and \(h(n)\), the cost to get from that node to the goal (or estimated cost), given by the formula \(f(n)=g(n)+h(n)\), where \(f(n)\) represents the estimated total cost of the cheapest solution path passing through node \(n\). Since \(g(n)\) gives the path cost from the start node to node \(n\), and \(h(n)\) is the estimated cost of the cheapest path from n to the goal, \(f(n)\) estimates the cost of the cheapest solution through \(n\). Thus, as the objective is to try to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of \(g(n)+h(n)\). It turns out that this strategy is more than just reasonable. Provided that the heuristic function \(h(n)\) satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to uniform cost search, except that A* uses \(g(n)+h(n)\) instead of \(g(n)\).  
The A* algorithm combines the strengths of two other algorithms: [PERSON]'s algorithm, tries to find the shortest path to all nodes from a single source node, and the greedy best-first search, and explores the node that appears to be closest to the goal, based on a heuristic function. The general A* process can be described by the following Algorithm 1:  
```
1 Variables:
2 OPEN listInitialize as an empty list
3 node_goalCreate the goal node;
4 CLOSED_listInitialize as an empty list
5 node_start:Create start node;
6 Add node_start to the OPEN_list
7 while the OPEN_list is not empty do
8 Get node n off the OPEN_list with the lowest \(f(n)\)
9 Add n to the CLOSED_list
10 if\(n\) is the same as node_goal then
11 return Solution(\(n\))
12 Else
13 Generate each successor node \(n\)' of \(n\)
14 for each successor node \(n\)' of \(n\)do
15 Set the parent of \(n\)' to \(n\)
16 Set \(h(n\)') to be the heuristically estimate distance to node_goal
17 Set \(g(n\)') to be \(g(n)\) plus the cost to get to \(n\)' from \(n\)
18 Set \(f(n\)') to be \(g(n\)') plus \(h(n\)')
19 if\(n\) is on the OPEN_list and the existing one is as good or better then
20 discard \(n\)' and continue
21 if\(n\) is on the CLOSED_list and the existing one is as good or better then
22 [ discard \(n\)' and continue
23 Remove occurrences of \(n\)' from OPEN_list and CLOSED_list
24 Add \(n\)' to the OPEN_list
```  
**Algorithm 1**A* algorithm pseudocode [29; 44].  
As we described in the literature review section, several studies have explored A* and have evidenced some limitations. For example, although the A* algorithm may find a path much quicker than uninformed search, it does not ensure that the result will be the shortest path [42]. Given the challenge in the definition of the heuristic function of the A* algorithm, many heuristic functions have been studied [70] and developed. One of the common heuristic functions in pathfinding is heuristic distance, such as diagonal distance, Manhattan distance and others [42]. Other studies [21; 31; 32; 33; 34; 43; 51; 71] have extended the A* formalism with other heuristics and methods.