it is a graph for cities and i need to find the fast and best path to reach the goal that's goes well but I don't know how to find the cost of the path
<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)
What I have tried:
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
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
return f_cost, last_node