A* Algorithm

Time complexity: O(b)d

Space complexity: O(b)d

Data type: Graphs

Visualization

React Flow
Click any two vertices to connect them
Shift+click on the node to set it as "start"
Ctrl+click on the node to set it as "end"
Shift+click on arrow to increase weight
Ctrl+click on arrow to decrease weight

Definition

A* is an informed search algorithm that finds the shortest path between two nodes in a graph. It uses a heuristic function to estimate the cost from the current node to the goal, prioritizing nodes that appear to be on the shortest path.

Constraints

  • Requires an admissible heuristic (never overestimates the true cost)
  • Graph edges must have non-negative weights
  • Optimal for grids and graphs with consistent heuristics

Step-by-step explanation

Arguments:

  • Graph representation - graph
  • Start node - start
  • Goal node - goal
  • Heuristic function - h(n)

Explanation:

  • Initialize open set with start node (f(n) = g(n) + h(n))
  • Initialize closed set (empty)
  • While open set is not empty:
    • Select node with lowest f(n) from open set
    • If current node is goal, return path
    • Generate current node's neighbors
    • For each neighbor:
      • Calculate tentative g score
      • If better path found, update neighbor's values
      • Add to open set if not already there
    • Move current node to closed set

Returns:

The shortest path from start to goal (if one exists), or indication that no path exists

Example

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <unordered_set>
5
#include <limits>
6


7
struct Node {
8
    int vertex;
9
    int f_cost;
10


11
    bool operator>(const Node& other) const {
12
        return f_cost > other.f_cost;
13
    }
14
};
15


16
std::vector<int> aStar(
17
    const std::vector<std::vector<std::pair<int, int>>>& graph,
18
    const std::vector<int>& heuristic,
19
    int start,
20
    int goal
21
) {
22
    int n = graph.size();
23
    std::vector<int> g_cost(n, std::numeric_limits<int>::max());
24
    std::vector<int> came_from(n, -1);
25


26
    g_cost[start] = 0;
27


28
    std::priority_queue<Node, std::vector<Node>, std::greater<>> open_set;
29
    open_set.push({start, heuristic[start]});
30


31
    while (!open_set.empty()) {
32
        int current = open_set.top().vertex;
33
        open_set.pop();
34


35
        if (current == goal)
36
            break;
37


38
        for (auto [neighbor, weight] : graph[current]) {
39
            int tentative_g = g_cost[current] + weight;
40


41
            if (tentative_g < g_cost[neighbor]) {
42
                came_from[neighbor] = current;
43
                g_cost[neighbor] = tentative_g;
44
                int f = tentative_g + heuristic[neighbor];
45
                open_set.push({neighbor, f});
46
            }
47
        }
48
    }
49


50
    // Return reconstructed path
51
    std::vector<int> path;
52
    for (int v = goal; v != -1; v = came_from[v])
53
        path.push_back(v);
54
    std::reverse(path.begin(), path.end());
55
    return path;
56
}