A* Algorithm

A* is an informed search algorithm that finds the shortest path using both the actual distance from the start and an estimated distance to the goal (heuristic). It's optimal and efficient for pathfinding in games and robotics.

A* Algorithm Visualization

ghf

Velocidade

OPEN

CLOSED

Complexity

Time Complexity: O(b^d)

Space Complexity: O(b^d)

Pseudocode

function AStar(start, goal):
  openSet = {start}
  gScore = {start: 0}
  fScore = {start: heuristic(start, goal)}
  
  while openSet is not empty:
    current = node with lowest fScore
    if current == goal:
      return reconstruct_path(cameFrom, current)
    
    for each neighbor:
      tentative_g = gScore[current] + distance(current, neighbor)
      if tentative_g < gScore[neighbor]:
        cameFrom[neighbor] = current
        gScore[neighbor] = tentative_g
        fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)

Related Algorithms

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue and is widely used in routing and network protocols.

Time: O((V + E) log V) | Space: O(V)

Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth level before moving to vertices at the next depth level. It uses a queue data structure and is useful for finding shortest paths in unweighted graphs.

Time: O(V + E) | Space: O(V)