A* Algorithm implementation

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