Untitled

import heapq

graph = {
    "P": {'Q': [1, 6], 'R': [4, 2]},
    "Q": {'T': [12, 0], 'S': [5, 1], 'R': [2, 2]},
    "R": {'S': [2, 1]},
    "S": {'T': [3, 0]},
    "T": {}
}


def astar(graph, start_node, goal_node):
    f_distance = {node: float('inf') for node in graph}
    f_distance[start_node] = 0
    g_distance = {node: float('inf') for node in graph}
    g_distance[start_node] = 0

    parent = {node: None for node in graph}
    parent[start_node] = None

    priority_queue = [(0, start_node)]

    while priority_queue:
        current_f_distance, current_node = heapq.heappop(priority_queue)

        if current_node == goal_node:
            return f_distance, parent
        for next_node, weights in graph[current_node].items():  # First Read [('Q', [1, 6]), ('R', [4, 2])]
            temp_g_distance = g_distance[current_node] + weights[0] # val = 1

            if temp_g_distance < g_distance[next_node]:
                g_distance[next_node] = temp_g_distance
                heuristic = weights[1]
                f_distance[next_node] = temp_g_distance + heuristic
                parent[next_node] = current_node
            heapq.heappush(priority_queue, (f_distance[next_node], next_node))

    return f_distance, parent


start_node = 'P'
goal_node = 'T'
f_distance, parent = astar(graph, start_node, goal_node)

# print(parent)
node = goal_node
path = []
while node is not None:
    path.append(node)
    node = parent[node]
path.reverse()
print("The path is: ", path)
print("Path cost is: ", f_distance.get(goal_node))