astar.py

# class Graph:
# list of edges with cost
# heuristic of each edge
class Graph:

    def __init__(self):
        self.edges = {
            'S': [('A', 6), ('B', 5), ('C', 10)],
            'A': [('E', 4)],
            'B': [('E', 6), ('D', 7)],
            'C': [('D', 2)],
            'D': [('F', 6)],
            'E': [('F', 4)],
            'F': [('G', 3)]
        }
        self.weights = {
            'S': 17,
            'A': 10,
            'B': 13,
            'C': 4,
            'D': 2,
            'E': 4,
            'F': 3,
            'G': 0
        }

    def neighbors(self, vertex):
        return self.edges.get(vertex)

graph = Graph()

visited_vertices = []

visited_vertices.append('S')

for vertex in visited_vertices:
    cost_so_far = 9999
    da_neighbor = 'X'
    # If we are at the goal state, stop!
    if vertex == 'G': break
    # For every node which is neighbor to current node
    for neighbor, movement_cost_to_neighbor in graph.neighbors(vertex):
        # Calculate cost to that node
        #   f(n)               = g(n)                      + h(n)
        total_cost_to_neighbor = movement_cost_to_neighbor + graph.weights.get(neighbor)
        # If that node is not in path, and the cost is lesser than the previous neighbor (yay)
        if neighbor not in visited_vertices and total_cost_to_neighbor < cost_so_far:
            # Place the node in path
            da_neighbor = neighbor
    visited_vertices.append(da_neighbor)

print(visited_vertices)