AiSc 7

# Graph layout
graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("D", 5)],
    "C": [("D", 1)],
    "D": [],
}

# Heuristic values
heuristic = {"A": 6, "B": 4, "C": 1, "D": 0}


def a_star_search(start, goal):
    # Queue format: (f, g, path)
    queue = [(heuristic[start], 0, [start])]
    visited = set()

    while queue:
        # Sort by lowest f(n)
        queue.sort(key=lambda x: x[0])

        f, g, path = queue.pop(0)
        node = path[-1]

        if node == goal:
            return path, g

        if node not in visited:
            visited.add(node)

            for neighbor, cost in graph.get(node, []):
                new_g = g + cost
                new_f = new_g + heuristic[neighbor]

                queue.append((new_f, new_g, path + [neighbor]))

    return None, float("inf")


# Execute A* search from A to D
optimal_path, total_cost = a_star_search("A", "D")

print(f"Optimal A* Path: {optimal_path}")
print(f"Total Path Cost: {total_cost}")