# Untitled

unknown

python

2 years ago

1.6 kB

4

Indexable

Never

^{}

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