fork download
copy 
  1. # Define the graph
  2. graph = {
  3.     'A': {'D': 3, 'B': 5, 'C': 8},
  4.     'D': {'F': 7},
  5.     'B': {'E': 2},
  6.     'C': {'F': 3, 'E': 3},
  7.     'F': {'G': 1},
  8.     'E': {'H': 1},
  9.     'H': {'G': 2}
  10. }
  11.  
  12. # Define heuristic values
  13. heuristic = {
  14.     'A': 40,
  15.     'D': 35,
  16.     'B': 32,
  17.     'C': 25,
  18.     'E': 19,
  19.     'F': 17,
  20.     'H': 10,
  21.     'G': 0  # Goal
  22. }
  23.  
  24. def a_star_algorithm(start, goal):
  25.     # Open list as a simple list of tuples (total_cost, node)
  26.     open_list = [(0, start)]
  27.  
  28.     # Dictionary to store the cost of reaching each node
  29.     g_costs = {start: 0}
  30.  
  31.     # Dictionary to reconstruct the path
  32.     came_from = {}
  33.  
  34.     while open_list:
  35.         # Sort the open list by the first element (f_cost) and pop the smallest
  36.         open_list.sort()
  37.         _, current = open_list.pop(0)
  38.  
  39.         if current == goal:
  40.             # Reconstruct the path
  41.             path = []
  42.             while current in came_from:
  43.                 path.append(current)
  44.                 current = came_from[current]
  45.             path.append(start)
  46.             path.reverse()
  47.             return path, g_costs[goal]
  48.  
  49.         # Process neighbors
  50.         for neighbor, weight in graph.get(current, {}).items():
  51.             tentative_g_cost = g_costs[current] + weight
  52.             if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
  53.                 g_costs[neighbor] = tentative_g_cost
  54.                 f_cost = tentative_g_cost + heuristic[neighbor]
  55.                 open_list.append((f_cost, neighbor))
  56.                 came_from[neighbor] = current
  57.  
  58.     return None, float('inf')  # If no path is found
  59.  
  60. # Run the A* algorithm
  61. start_node = 'A'
  62. goal_node = 'G'
  63. path, cost = a_star_algorithm(start_node, goal_node)
  64.  
  65. print("Path:", path)
  66. print("Cost:", cost)
Success #stdin #stdout 0.12s 14192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Path: ['A', 'C', 'F', 'G']
Cost: 12
https://ideone.com/hYZUaq
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!