# 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):
# Open list as a simple list of tuples (total_cost, node)
open_list = [(0, start)]
# Dictionary to store the cost of reaching each node
g_costs = {start: 0}
# Dictionary to reconstruct the path
came_from = {}
while open_list:
# Sort the open list by the first element (f_cost) and pop the smallest
open_list.sort()
_, current = open_list.pop(0)
if current == goal:
# Reconstruct the path
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path, g_costs[goal]
# Process neighbors
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_list.append((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)
IyBEZWZpbmUgdGhlIGdyYXBoCmdyYXBoID0gewogICAgJ0EnOiB7J0QnOiAzLCAnQic6IDUsICdDJzogOH0sCiAgICAnRCc6IHsnRic6IDd9LAogICAgJ0InOiB7J0UnOiAyfSwKICAgICdDJzogeydGJzogMywgJ0UnOiAzfSwKICAgICdGJzogeydHJzogMX0sCiAgICAnRSc6IHsnSCc6IDF9LAogICAgJ0gnOiB7J0cnOiAyfQp9CgojIERlZmluZSBoZXVyaXN0aWMgdmFsdWVzCmhldXJpc3RpYyA9IHsKICAgICdBJzogNDAsCiAgICAnRCc6IDM1LAogICAgJ0InOiAzMiwKICAgICdDJzogMjUsCiAgICAnRSc6IDE5LAogICAgJ0YnOiAxNywKICAgICdIJzogMTAsCiAgICAnRyc6IDAgICMgR29hbAp9CgpkZWYgYV9zdGFyX2FsZ29yaXRobShzdGFydCwgZ29hbCk6CiAgICAjIE9wZW4gbGlzdCBhcyBhIHNpbXBsZSBsaXN0IG9mIHR1cGxlcyAodG90YWxfY29zdCwgbm9kZSkKICAgIG9wZW5fbGlzdCA9IFsoMCwgc3RhcnQpXQogICAgCiAgICAjIERpY3Rpb25hcnkgdG8gc3RvcmUgdGhlIGNvc3Qgb2YgcmVhY2hpbmcgZWFjaCBub2RlCiAgICBnX2Nvc3RzID0ge3N0YXJ0OiAwfQogICAgCiAgICAjIERpY3Rpb25hcnkgdG8gcmVjb25zdHJ1Y3QgdGhlIHBhdGgKICAgIGNhbWVfZnJvbSA9IHt9CiAgICAKICAgIHdoaWxlIG9wZW5fbGlzdDoKICAgICAgICAjIFNvcnQgdGhlIG9wZW4gbGlzdCBieSB0aGUgZmlyc3QgZWxlbWVudCAoZl9jb3N0KSBhbmQgcG9wIHRoZSBzbWFsbGVzdAogICAgICAgIG9wZW5fbGlzdC5zb3J0KCkKICAgICAgICBfLCBjdXJyZW50ID0gb3Blbl9saXN0LnBvcCgwKQogICAgICAgIAogICAgICAgIGlmIGN1cnJlbnQgPT0gZ29hbDoKICAgICAgICAgICAgIyBSZWNvbnN0cnVjdCB0aGUgcGF0aAogICAgICAgICAgICBwYXRoID0gW10KICAgICAgICAgICAgd2hpbGUgY3VycmVudCBpbiBjYW1lX2Zyb206CiAgICAgICAgICAgICAgICBwYXRoLmFwcGVuZChjdXJyZW50KQogICAgICAgICAgICAgICAgY3VycmVudCA9IGNhbWVfZnJvbVtjdXJyZW50XQogICAgICAgICAgICBwYXRoLmFwcGVuZChzdGFydCkKICAgICAgICAgICAgcGF0aC5yZXZlcnNlKCkKICAgICAgICAgICAgcmV0dXJuIHBhdGgsIGdfY29zdHNbZ29hbF0KICAgICAgICAKICAgICAgICAjIFByb2Nlc3MgbmVpZ2hib3JzCiAgICAgICAgZm9yIG5laWdoYm9yLCB3ZWlnaHQgaW4gZ3JhcGguZ2V0KGN1cnJlbnQsIHt9KS5pdGVtcygpOgogICAgICAgICAgICB0ZW50YXRpdmVfZ19jb3N0ID0gZ19jb3N0c1tjdXJyZW50XSArIHdlaWdodAogICAgICAgICAgICBpZiBuZWlnaGJvciBub3QgaW4gZ19jb3N0cyBvciB0ZW50YXRpdmVfZ19jb3N0IDwgZ19jb3N0c1tuZWlnaGJvcl06CiAgICAgICAgICAgICAgICBnX2Nvc3RzW25laWdoYm9yXSA9IHRlbnRhdGl2ZV9nX2Nvc3QKICAgICAgICAgICAgICAgIGZfY29zdCA9IHRlbnRhdGl2ZV9nX2Nvc3QgKyBoZXVyaXN0aWNbbmVpZ2hib3JdCiAgICAgICAgICAgICAgICBvcGVuX2xpc3QuYXBwZW5kKChmX2Nvc3QsIG5laWdoYm9yKSkKICAgICAgICAgICAgICAgIGNhbWVfZnJvbVtuZWlnaGJvcl0gPSBjdXJyZW50CiAgICAKICAgIHJldHVybiBOb25lLCBmbG9hdCgnaW5mJykgICMgSWYgbm8gcGF0aCBpcyBmb3VuZAoKIyBSdW4gdGhlIEEqIGFsZ29yaXRobQpzdGFydF9ub2RlID0gJ0EnCmdvYWxfbm9kZSA9ICdHJwpwYXRoLCBjb3N0ID0gYV9zdGFyX2FsZ29yaXRobShzdGFydF9ub2RlLCBnb2FsX25vZGUpCgpwcmludCgiUGF0aDoiLCBwYXRoKQpwcmludCgiQ29zdDoiLCBjb3N0KQ==