15,560,678 members

Python

<pre>import heapq graph ={ 'Khafji': {'Jubail':[100,2]}, 'Jubail': {'Hofuf':[140,5],'Dammam':[80,4]}, 'Dammam': {'Bahrain':[20,4]}, 'Hofuf': {'Riyadh': [300,4]}, 'Bahrain': {'Doha':[50,2]}, 'Riyadh': {'Doha': [320,2], 'Abu Dhabi': [600,5]}, 'Doha' : {'Abu Dhabi': [400,5]}, 'Abu Dhabi': {'Dubai': [120,0]}, 'Dubai': {} } 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(): temp_g_distance = g_distance[current_node] + weights[0] 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 =input('Enter the initial vertex: ') goal_node = input('Enter the goal vertex: ') f_distance, parent = astar(graph, start_node, goal_node) def print_path(f_distance, parent, start_node, goal_node): node = goal_node path = [] while node != None: path.append(node) node = parent[node] path.reverse() print("The path is: ", path) print_path(f_distance, parent, start_node, goal_node)

i tried to use this function first i start by separate the edges from the huristic each one in own table than i use this algorithm

Python

def priority_queue(path): g_cost = 0 for(node, cost) in path: g_cost += cost last_node = path[-1][0] H_cost = h_table[last_node] f_cost = g_cost + H_cost # print('path cost: ', path) return f_cost, last_node

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900