Click here to Skip to main content
15,560,678 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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
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)


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
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
Posted
Updated 5-Mar-22 8:38am

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