Untitled

import pandas as pd

# Define the graph as adjacency list with weights
graph = {
    'S': {'A': 2, 'D': 3},
    'A': {'S': 2, 'B': 3, 'D': 2},
    'B': {'A': 3, 'C': 3},
    'C': {'B': 3, 'G': 5},
    'D': {'S': 3, 'A': 2, 'E': 6},
    'E': {'D': 6, 'F': 1},
    'F': {'E': 1, 'G': 2},
    'G': {'C': 5, 'F': 2}
}

# Define the heuristic values
heuristic = {
    'S': 8,
    'A': 6,
    'B': 5,
    'C': 3,
    'D': 6,
    'E': 3,
    'F': 1,
    'G': 0
}

# A* Algorithm implementation
def a_star_search(graph, heuristic, start, goal):
    open_list = {start: (0 + heuristic[start])}  # Open list with initial node and its f(n) value
    closed_list = set()  # Closed list
    g_values = {start: 0}  # Cost from start to node
    parent = {start: None}  # To reconstruct the path

    while open_list:
        # Get the node with the lowest f(n) value
        current_node = min(open_list, key=open_list.get)
        current_f_value = open_list[current_node]

        # If goal is reached, reconstruct the path
        if current_node == goal:
            path = []
            while current_node:
                path.append(current_node)
                current_node = parent[current_node]
            path.reverse()
            return path, g_values[goal]  # Return the path and its cost

        # Move current_node from open to closed list
        del open_list[current_node]
        closed_list.add(current_node)

        # Check neighbors of the current node
        for neighbor, cost in graph[current_node].items():
            if neighbor in closed_list:
                continue  # Skip if neighbor is in closed list

            # Calculate tentative g value for the neighbor
            tentative_g = g_values[current_node] + cost

            if neighbor not in open_list or tentative_g < g_values.get(neighbor, float('inf')):
                g_values[neighbor] = tentative_g  # Update g value
                f_value = tentative_g + heuristic[neighbor]  # Calculate f value
                open_list[neighbor] = f_value  # Add/update neighbor in open list
                parent[neighbor] = current_node  # Update parent

    return None, float('inf')  # Return None if no path is found

# Perform A* search from S to G
path, cost = a_star_search(graph, heuristic, 'S', 'G')

# Prepare results for display
results = {
    "Path": [path],
    "Total Cost": [cost]
}
df_results = pd.DataFrame(results)
import ace_tools as tools; tools.display_dataframe_to_user(name="A* Algorithm Path and Cost", dataframe=df_results)