Play this article

### Formula f(n)=g(n)+h(n)

tc O(N+h)

sc O(n+h)

```
import heapq
def astar(start, goal, graph, heuristic):
"""
A* algorithm implementation.
Args:
start: Start node.
goal: Goal node.
graph: Graph represented as a dictionary of dictionaries.
heuristic: Heuristic function.
Returns:
Path from start to goal.
"""
frontier = [(0, start)]
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
# Define the heuristic values for each node in an array
heuristic_values = [14, 12, 11, 6, 4, 11, 0]
while frontier:
current = heapq.heappop(frontier)[1]
if current == goal:
break
for next_node in graph[current]:
new_cost = cost_so_far[current] + graph[current][next_node]
# Use the heuristic value from the array
heuristic_value = heuristic_values[ord(next_node) - ord('A')]
if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
cost_so_far[next_node] = new_cost
priority = new_cost + heuristic_value
heapq.heappush(frontier, (priority, next_node))
came_from[next_node] = current
path = []
current = goal
while current != start:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path
graph = {
'S': {
'B': 4,
'C': 3
},
'B': {
'E': 12,
'F': 5
},
'C': {
'E': 10,
'D': 7
},
'D': {
'E': 4
},
'E': {
'G': 5
},
'F': {
'G': 16
},
'G': {}
}
def heuristic(a, b):
return abs(ord(a) - ord(b))
path = astar('S', 'G', graph, heuristic)
print(path)
```

### Approach Two

```
from collections import deque
class Graph:
def __init__(self, adjacency_list):
self.adjacency_list = adjacency_list
def get_neighbors(self, v):
return self.adjacency_list[v]
def h(self, n):
H = {'S': 14, 'C': 11, 'B': 12, 'F': 11, 'D': 6, 'E': 4, 'G': 0}
return H[n]
def a_star_algorithm(self, start_node, stop_node):
open_list = set([start_node])
closed_list = set([])
g = {}
g[start_node] = 0
parents = {}
parents[start_node] = start_node
while len(open_list) > 0:
n = None
for v in open_list:
if n == None or g[v] + self.h(v) < g[n] + self.h(n):
n = v
if n == None:
print('Path does not exist!')
return None
# if the current node is the stop_node
# then we begin reconstructin the path from it to the start_node
if n == stop_node:
reconst_path = []
while parents[n] != n:
reconst_path.append(n)
n = parents[n]
reconst_path.append(start_node)
reconst_path.reverse()
print('Path found: {}'.format(reconst_path))
return reconst_path
# for all neighbors of the current node do
for (m, weight) in self.get_neighbors(n):
# if the current node isn't in both open_list and closed_list
# add it to open_list and note n as it's parent
if m not in open_list and m not in closed_list:
open_list.add(m)
parents[m] = n
g[m] = g[n] + weight
# otherwise, check if it's quicker to first visit n, then m
# and if it is, update parent data and g data
# and if the node was in the closed_list, move it to open_list
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_list:
closed_list.remove(m)
open_list.add(m)
# remove n from the open_list, and add it to closed_list
# because all of his neighbors were inspected
open_list.remove(n)
closed_list.add(n)
print('Path does not exist!')
return None
adjacency_list = {
'S': [('B', 4), ('C', 3)],
'B': [('F', 5), ('E', 12)],
'C': [('D', 7), ('E', 10)],
'D': [('E', 2)],
'E': [('G', 5)],
'F': [('G', 16)],
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('S', 'G')
```