def astar(graph, start, goal):
open_set = {start}
came_from = {}
g_scores = {start: 0}
f_scores = {start: 0}
while open_set:
current = min(open_set, key=lambda node: f_scores[node])
if current == goal:
path = []
while current != start:
path.append(current)
current = came_from[current]
return [start] + path[::-1]
open_set.remove(current)
for neighbor, cost in graph[current].items():
tentative_g_score = g_scores[current] + cost
if neighbor not in g_scores or tentative_g_score < g_scores[neighbor]:
came_from[neighbor] = current
g_scores[neighbor] = tentative_g_score
f_scores[neighbor] = g_scores[neighbor]
open_set.add(neighbor)
return None
graph = {
'A': {'B': 5, 'C': 2},
'B': {'D': 1, 'E': 6},
'C': {'F': 3},
'D': {},
'E': {'F': 4},
'F': {}
}
start_node = 'A'
goal_node = 'F'
path = astar(graph, start_node, goal_node)
print("Best path:", path) if path else print("Path not found.")
