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))