# ANICREATE  # A* Algorithm implementation

## Easy approaches

### 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)

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 get_neighbors(self, 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:
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)

# remove n from the open_list, and add it to closed_list
# because all of his neighbors were inspected
open_list.remove(n)

print('Path does not exist!')
return None

'S': [('B', 4), ('C', 3)],
'B': [('F', 5), ('E', 12)],
'C': [('D', 7), ('E', 10)],
'D': [('E', 2)],
'E': [('G', 5)],
'F': [('G', 16)],
}