Report

import heapq

def a_star(graph, heuristic, start, goal):
    visited = set()  # Set to keep track of visited nodes
    open_set = [(0 + heuristic[start], start)]  # Priority queue with initial node and its heuristic value
    came_from = {}  # Dictionary to keep track of the parent node for each node in the path
    g_score = {start: 0}  # Dictionary to store the cost to reach a node from the start node

    while open_set:
        _, current_node = heapq.heappop(open_set)  # Get the node with the smallest f-cost from the priority queue
        visited.add(current_node)  # Mark the current node as visited

        if current_node == goal:  # Check if the current node is the goal node
            return reconstruct_path(came_from, current_node)  # Reconstruct the path and return it

        neighbors = graph[current_node]  # Get the neighboring nodes of the current node
        for neighbor, cost in neighbors:  # Iterate over the neighboring nodes
            if neighbor not in visited:  # Check if the neighbor node has not been visited
                new_g_score = g_score[current_node] + cost  # Calculate the new g-score for the neighbor
                if neighbor not in g_score or new_g_score < g_score[neighbor]:
                    g_score[neighbor] = new_g_score  # Update the g-score for the neighbor if it's better
                    f_cost = new_g_score + heuristic[neighbor]  # Calculate the f-cost for the neighbor
                    heapq.heappush(open_set, (f_cost, neighbor))  # Add the neighbor to the priority queue with its f-cost
                    came_from[neighbor] = current_node  # Set the current node as the parent for the neighbor

    return None  # Return None if the goal node is not found

def reconstruct_path(came_from, current):
    path = []
    while current in came_from:  # Reconstruct the path from the goal node to the start node
        path.append(current)
        current = came_from[current]
    path.append(current)
    return path[::-1]  # Return the reversed path to get the path from the start node to the goal node

# Example usage
graph = {
    'S': [('A', 1), ('G', 10)],
    'A': [('B', 2), ('C', 1)],
    'B': [('D', 5)],
    'C': [('D', 3), ('G', 4)],
    'D': [('G', 2)],
    'G': []
}

heuristic = {
    'S': 5,
    'A': 3,
    'B': 4,
    'C': 2,
    'D': 6,
    'G': 0
}

start_node = 'S'
goal_node = 'G'  # Change 'H' to 'G' since the graph does not contain an 'H' node

result = a_star(graph, heuristic, start_node, goal_node)  # Perform A* search
if result:
    print("Optimal Path:", ' --> '.join(result))  # Print the optimal path if found
else:
    print("No path found.")  # Print if no path is found