def aStarAlgo(start_node, stop_node):
open_set = set(start_node)
closed_set = set()
g = {}
parents = {}
g[start_node] = 0
parents[start_node] = start_node
while len(open_set) > 0:
n = None
#choose the node which is having lowest f(n) which is calculated as g(n)+h(n)
for v in open_set:
if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v
#print("Node to expand is ",n)
if n == stop_node or Graph_nodes[n] == None:
#print("No more nieghbours")
pass
else:
for (m, weight) in get_neighbors(n):
if m not in open_set and m not in closed_set: # visiting child for the first time
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
#print("Open List:",open_set)
#print("Closed List:",closed_set)
#print("Parent list:",parents)
#print("g(n) list:",g)
if n == None:
print('Path does not exist!')
return None
#printing the path by finding the parent of each node from the goal node
if n == stop_node:
path = []
while parents[n] != n:
path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print('Path found: {}'.format(path))
return path

remove n from the open_list, and add it to closed_list

because all of his neighbors were inspected

open_set.remove(n)
closed_set.add(n)
print('Path does not exist!')
return None
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,
}
return H_dist[n]
Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1), ('G', 9)],
'C': None,
'E': [('D', 6)],
'D': [('G', 1)],
}
aStarAlgo('A', 'G')