from queue import PriorityQueue
 
# Define the graph
graph = {
    'A': {'D': 3, 'B': 5, 'C': 8},
    'D': {'F': 7},
    'B': {'E': 2},
    'C': {'F': 3, 'E': 3},
    'F': {'G': 1},
    'E': {'H': 1},
    'H': {'G': 2}
}
 
# Define heuristic values
heuristic = {
    'A': 40,
    'D': 35,
    'B': 32,
    'C': 25,
    'E': 19,
    'F': 17,
    'H': 10,
    'G': 0  # Goal
}
 
def a_star_algorithm(start, goal):
    # Priority queue to store nodes along with their cost
    open_set = PriorityQueue()
    open_set.put((0, start))  # (total_cost, node)
 
    # Dictionary to store the cost of reaching each node
    g_costs = {start: 0}
 
    # Dictionary to reconstruct the path
    came_from = {}
 
    while not open_set.empty():
        _, current = open_set.get()
 
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path, g_costs[goal]
 
        for neighbor, weight in graph.get(current, {}).items():
            tentative_g_cost = g_costs[current] + weight
            if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
                g_costs[neighbor] = tentative_g_cost
                f_cost = tentative_g_cost + heuristic[neighbor]
                open_set.put((f_cost, neighbor))
                came_from[neighbor] = current
 
    return None, float('inf')  # If no path is found
 
# Run the A* algorithm
start_node = 'A'
goal_node = 'G'
path, cost = a_star_algorithm(start_node, goal_node)
 
print("Path:", path)
print("Cost:", cost)

ZnJvbSBxdWV1ZSBpbXBvcnQgUHJpb3JpdHlRdWV1ZQoKIyBEZWZpbmUgdGhlIGdyYXBoCmdyYXBoID0gewogICAgJ0EnOiB7J0QnOiAzLCAnQic6IDUsICdDJzogOH0sCiAgICAnRCc6IHsnRic6IDd9LAogICAgJ0InOiB7J0UnOiAyfSwKICAgICdDJzogeydGJzogMywgJ0UnOiAzfSwKICAgICdGJzogeydHJzogMX0sCiAgICAnRSc6IHsnSCc6IDF9LAogICAgJ0gnOiB7J0cnOiAyfQp9CgojIERlZmluZSBoZXVyaXN0aWMgdmFsdWVzCmhldXJpc3RpYyA9IHsKICAgICdBJzogNDAsCiAgICAnRCc6IDM1LAogICAgJ0InOiAzMiwKICAgICdDJzogMjUsCiAgICAnRSc6IDE5LAogICAgJ0YnOiAxNywKICAgICdIJzogMTAsCiAgICAnRyc6IDAgICMgR29hbAp9CgpkZWYgYV9zdGFyX2FsZ29yaXRobShzdGFydCwgZ29hbCk6CiAgICAjIFByaW9yaXR5IHF1ZXVlIHRvIHN0b3JlIG5vZGVzIGFsb25nIHdpdGggdGhlaXIgY29zdAogICAgb3Blbl9zZXQgPSBQcmlvcml0eVF1ZXVlKCkKICAgIG9wZW5fc2V0LnB1dCgoMCwgc3RhcnQpKSAgIyAodG90YWxfY29zdCwgbm9kZSkKICAgIAogICAgIyBEaWN0aW9uYXJ5IHRvIHN0b3JlIHRoZSBjb3N0IG9mIHJlYWNoaW5nIGVhY2ggbm9kZQogICAgZ19jb3N0cyA9IHtzdGFydDogMH0KICAgIAogICAgIyBEaWN0aW9uYXJ5IHRvIHJlY29uc3RydWN0IHRoZSBwYXRoCiAgICBjYW1lX2Zyb20gPSB7fQogICAgCiAgICB3aGlsZSBub3Qgb3Blbl9zZXQuZW1wdHkoKToKICAgICAgICBfLCBjdXJyZW50ID0gb3Blbl9zZXQuZ2V0KCkKICAgICAgICAKICAgICAgICBpZiBjdXJyZW50ID09IGdvYWw6CiAgICAgICAgICAgIHBhdGggPSBbXQogICAgICAgICAgICB3aGlsZSBjdXJyZW50IGluIGNhbWVfZnJvbToKICAgICAgICAgICAgICAgIHBhdGguYXBwZW5kKGN1cnJlbnQpCiAgICAgICAgICAgICAgICBjdXJyZW50ID0gY2FtZV9mcm9tW2N1cnJlbnRdCiAgICAgICAgICAgIHBhdGguYXBwZW5kKHN0YXJ0KQogICAgICAgICAgICBwYXRoLnJldmVyc2UoKQogICAgICAgICAgICByZXR1cm4gcGF0aCwgZ19jb3N0c1tnb2FsXQogICAgICAgIAogICAgICAgIGZvciBuZWlnaGJvciwgd2VpZ2h0IGluIGdyYXBoLmdldChjdXJyZW50LCB7fSkuaXRlbXMoKToKICAgICAgICAgICAgdGVudGF0aXZlX2dfY29zdCA9IGdfY29zdHNbY3VycmVudF0gKyB3ZWlnaHQKICAgICAgICAgICAgaWYgbmVpZ2hib3Igbm90IGluIGdfY29zdHMgb3IgdGVudGF0aXZlX2dfY29zdCA8IGdfY29zdHNbbmVpZ2hib3JdOgogICAgICAgICAgICAgICAgZ19jb3N0c1tuZWlnaGJvcl0gPSB0ZW50YXRpdmVfZ19jb3N0CiAgICAgICAgICAgICAgICBmX2Nvc3QgPSB0ZW50YXRpdmVfZ19jb3N0ICsgaGV1cmlzdGljW25laWdoYm9yXQogICAgICAgICAgICAgICAgb3Blbl9zZXQucHV0KChmX2Nvc3QsIG5laWdoYm9yKSkKICAgICAgICAgICAgICAgIGNhbWVfZnJvbVtuZWlnaGJvcl0gPSBjdXJyZW50CiAgICAKICAgIHJldHVybiBOb25lLCBmbG9hdCgnaW5mJykgICMgSWYgbm8gcGF0aCBpcyBmb3VuZAoKIyBSdW4gdGhlIEEqIGFsZ29yaXRobQpzdGFydF9ub2RlID0gJ0EnCmdvYWxfbm9kZSA9ICdHJwpwYXRoLCBjb3N0ID0gYV9zdGFyX2FsZ29yaXRobShzdGFydF9ub2RlLCBnb2FsX25vZGUpCgpwcmludCgiUGF0aDoiLCBwYXRoKQpwcmludCgiQ29zdDoiLCBjb3N0KQ==