1. def aStarAlgo(start_node, stop_node):
  2.          
  3.         open_set = set(start_node) 
  4.         closed_set = set()
  5.         g = {} #store distance from starting node
  6.         parents = {}# parents contains an adjacency map of all nodes
  7.  
  8.         #ditance of starting node from itself is zero
  9.         g[start_node] = 0
  10.         #start_node is root node i.e it has no parent nodes
  11.         #so start_node is set to its own parent node
  12.         parents[start_node] = start_node
  13.          
  14.          
  15.         while len(open_set) > 0:
  16.             n = None
  17.  
  18.             #node with lowest f() is found
  19.             for v in open_set:
  20.                 if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
  21.                     n = v
  22.              
  23.                      
  24.             if n == stop_node or Graph_nodes[n] == None:
  25.                 pass
  26.             else:
  27.                 for (m, weight) in get_neighbors(n):
  28.                     #nodes 'm' not in first and last set are added to first
  29.                     #n is set its parent
  30.                     if m not in open_set and m not in closed_set:
  31.                         open_set.add(m)
  32.                         parents[m] = n
  33.                         g[m] = g[n] + weight
  34.                          
  35.      
  36.                     #for each node m,compare its distance from start i.e g(m) to the
  37.                     #from start through n node
  38.                     else:
  39.                         if g[m] > g[n] + weight:
  40.                             #update g(m)
  41.                             g[m] = g[n] + weight
  42.                             #change parent of m to n
  43.                             parents[m] = n
  44.                              
  45.                             #if m in closed set,remove and add to open
  46.                             if m in closed_set:
  47.                                 closed_set.remove(m)
  48.                                 open_set.add(m)
  49.  
  50.             if n == None:
  51.                 print('Path does not exist!')
  52.                 return None
  53.  
  54.             # if the current node is the stop_node
  55.             # then we begin reconstructin the path from it to the start_node
  56.             if n == stop_node:
  57.                 path = []
  58.  
  59.                 while parents[n] != n:
  60.                     path.append(n)
  61.                     n = parents[n]
  62.  
  63.                 path.append(start_node)
  64.  
  65.                 path.reverse()
  66.  
  67.                 print('Path found: {}'.format(path))
  68.                 return path
  69.  
  70.  
  71.             # remove n from the open_list, and add it to closed_list
  72.             # because all of his neighbors were inspected
  73.             open_set.remove(n)
  74.             closed_set.add(n)
  75.  
  76.         print('Path does not exist!')
  77.         return None
  78.          
  79. #define fuction to return neighbor and its distance
  80. #from the passed node
  81. def get_neighbors(v):
  82.     if v in Graph_nodes:
  83.         return Graph_nodes[v]
  84.     else:
  85.         return None
  86. #for simplicity we ll consider heuristic distances given
  87. #and this function returns heuristic distance for all nodes
  88. def heuristic(n):
  89.         H_dist = {
  90.             'START': 550,
  91.             'A': 550,
  92.             'B': 450,
  93.             'C': 510,
  94.             'D': 325,
  95.             'E': 415,
  96.             'F': 235,
  97.             'G': 455,
  98.             'H': 400,
  99.             'I': 325,
  100.             'J': 240,
  101.             'K': 170,
  102.             'L': 205,
  103.             'GOAL': 0,
  104.              
  105.         }
  106.  
  107.         return H_dist[n]
  108.  
  109. #Input goes here  
  110. Graph_nodes = {
  111.     'START': [('A', 120), ('I', 142), ('G', 77)],
  112.     'A': [('B', 113)],
  113.     'B': [('C', 72)],
  114.     'C': [('D', 77)],
  115.     'D': [('E', 122)],
  116.     'E': [('F', 126)],
  117.     'F': [('L', 148), ('K', 140)],
  118.     'G': [('H', 71)],
  119.     'H': [('I', 122)],
  120.     'I': [('J', 111), ('L', 99)],
  121.     'J': [('GOAL', 213)],
  122.     'K': [('GOAL', 105)],
  123.     'L': [('K', 99)],
  124.      
  125. }
  126. aStarAlgo('START', 'GOAL')