A* Search Algorithm: Example, Java Code, Time Complexity

How does a satnav find the fastest path from start to destination in the least amount of time? This question (and similar ones) is addressed in this series of articles on “shortest path” algorithms.

In the last part, we noted that Dijkstra’s algorithm follows paths reachable from the starting point in all directions – regardless of the destination’s direction. Of course, this is not optimal.

The A* algorithm (pronounced “A star”) is a refinement of Dijkstra’s algorithm. The A* algorithm prematurely terminates the examination of paths leading in the wrong direction. For this purpose, it uses a heuristic that provides, with minimal effort, a lower bound for the remaining cost from each node to the destination. This article tells you exactly how it works.

The topics in detail:

• How does the A* algorithm work (explained step by step with an example)
• What distinguishes the A* algorithm from Dijkstra’s algorithm?
• How to implement the A* algorithm in Java?
• How to determine its time complexity?
• Measuring the runtime with TreeSet, PriorityQueue, and Fibonacci heap – and what lazy deletion changes about the PriorityQueue

You can find the source code for the entire article series in my GitHub repository.

A* Algorithm – Example

We start with an example. For simplicity, we use the same example as in the explanation of Dijkstra’s algorithm. The following drawing represents a road map:

Circles with letters represent locations. The lines in between are highways (thick lines), country roads (thin lines), and dirt roads (dashed lines).

We map the road map onto the following graph. Places become nodes; streets and paths become edges:

The weights of the edges represent the cost of a path. Costs are, for example, the time in minutes needed to traverse a path.

A shorter route does not necessarily lead to lower costs. For example, it may take significantly longer to pass a short dirt road than a longer highway.

We can now see, for example, that the shortest path from D to H is via F and takes a total of 11 minutes (yellow route). The longer route via C and G (blue route), on the other hand, takes only 9 minutes:

We humans can do that with a glance. We can navigate relatively easily, even on more complex road maps. The more experienced of us can probably remember looking at a road map instead of a satnav system.

A computer needs an algorithm for this purpose, e.g., the A* algorithm.

A* Algorithm – Heuristic Function

In the introduction, I mentioned a heuristic function that estimates the minimum remaining cost from each node of the graph to the destination node. Since our graph represents a two-dimensional map, a suitable heuristic is the Euclidean distance or – to put it briefly – the beeline to the destination node.

Later on, the heuristic will ensure that the algorithm prioritizes those nodes that roughly lead in the right direction.

The heuristic must never overestimate the actual costs that could be accumulated to the destination. To not overestimate the actual costs to the destination in the example, we calculate as a heuristic the number of minutes it would take to get to the destination on a highway following the beeline.

A heuristic that never overestimates is called admissible. Only with an admissible heuristic is A* guaranteed to find the fastest path. The implementation below requires a bit more: The heuristic must be consistent (also called “monotone”). That means: For every edge from node u to node v, remaining cost(u) ≤ cost(u–v) + remaining cost(v) – the estimated remainder must never drop by more than the edge’s cost. The beeline divided by the maximum speed satisfies this because the beeline obeys the triangle inequality, and no edge is faster than v_max. I explain why the implementation needs this in the section “Data Structure: Processed Nodes”.

To be able to measure distances, we add a coordinate system:

We now calculate the length of the two highways from A to C and from C to G using the Pythagorean theorem. Then we divide the length by the route’s cost to get the speed:

Path	Speed calculation
Path A–C	Distance: 3.415 km Cost: 2 min → Speed: 3.415 km / 2 min = 1.707 km/min (= 102.42 km/h)
Path C–G	Distance: 3.406 km Cost: 2 min → Speed: 3.406 km / 2 min = 1.703 km/min (= 102.18 km/h)

The fastest possible speed (v_max) on our map is achieved on route A–C and is about 1.7 km/min (this corresponds to 102 km/h ... or 63.4 mph).

Actually, we should calculate the speed for all roads. But we had initially constructed the map so that all other routes are slower. Therefore we skip that at this point.

In a satnav, the fastest possible speed is pre-calculated and included in the map data.

Applying the Heuristic Function

Using the fastest possible speed v_max, we now calculate the shortest possible travel time from each point on the map to the destination point. To do this, we calculate the Euclidean distance and divide it by v_max.

For node A, for example, as follows:

Node	Remaining cost calculation
Node A	Distance to target node H: 6.588 km vmax: 1.707 km/min → Minimum remaining cost: 6.588 km / 1.707 km/min = 3.859 min ≈ 3.9 min

We proceed in the same way for all other nodes. This results in the following shortest possible travel times (rounded to one decimal place):

Preparation – Table of Nodes

For further preparation, we create a table of nodes. The table has the following columns:

• Node name
• Predecessor node
• Total cost from the start node
• Minimum remaining cost to the target node
• Sum of both costs

The predecessor nodes remain empty for the time being. As total cost from the start, we fill in 0 for the start node. We set the total cost to infinity for all other nodes as we do not yet know whether we can reach them from the start node at all.

As minimum remaining costs, we enter the remaining costs to the destination node calculated in the previous section.

We then sort the table by the sum of the two cost columns (total cost from the start node + minimum remaining cost to the destination node). The nodes with a cost sum of infinity remain unsorted (in the example, they stay sorted alphabetically):

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
D	–	0.0	2.5	2.5
A	–	∞	3.9	∞
B	–	∞	4.3	∞
C	–	∞	3.2	∞
E	–	∞	2.5	∞
F	–	∞	1.5	∞
G	–	∞	2.8	∞
H	–	∞	0.0	∞
I	–	∞	1.6	∞

In the following sections, it is essential to distinguish the terms cost, total cost, and remaining cost:

• Cost denotes the cost from a node to its neighboring nodes.
• Total cost means the sum of all partial costs from the start node via any intermediate nodes to a specific node.
• Remaining costs denote the minimum costs calculated by the heuristic function that will still be accumulated on the way to the target.

In the literature, these three quantities are called g(n) for the total cost from the start to node n, h(n) for the estimated remaining cost (the heuristic), and f(n) = g(n) + h(n) for the cost sum by which the table is sorted.

The following diagram shows the three quantities for node C as they will appear in the table after the first step: the total cost from start D (distance driven) and the remaining cost to target H (beeline), and their sum:

A* Algorithm Step by Step – Processing the Nodes

In the following graphs, I include the respective predecessor node and the total and remaining costs in the nodes. This data is usually not included in the graph, but only in the table described above. Displaying them here will simplify the understanding.

Step 1: Examining All Neighbors of the Starting Point

We take the first element – node D – from the table and examine its neighbors, i.e., C, E, and F:

At this point, the neighboring nodes’ total costs are still at the initial value infinity, which means that we have not found any paths there yet. Now we have found ways there – namely directly from the starting point D.

Therefore, we enter the costs from D to the respective node as total costs from the start and calculate the sum with the remaining costs. We also fill in node D as the predecessor.

For C, for example, the following values result:

• Total cost from the start: 3.0 (the cost from D to C)
• Remaining cost: 3.2 (we calculated this for all nodes in the previous section)
• Sum of all costs: 3.0 + 3.2 = 6.2

For E and F, we proceed in the same way. For an easier understanding, I add the results to the graph:

We sort the updated table again by the sum of the costs (the changed entries are marked in bold):

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
E	D	1.0	2.5	3.5
F	D	4.0	1.5	5.5
C	D	3.0	3.2	6.2
A	–	∞	3.9	∞
B	–	∞	4.3	∞
G	–	∞	2.8	∞
H	–	∞	0.0	∞
I	–	∞	1.6	∞

The changes read like this: Nodes E, F, and C have been discovered. They can be reached via D in 1, 4, and 3 minutes, respectively. Adding the minimum remaining costs to the destination results in 3.5, 5.5, and 6.2 minutes that would be needed at least to reach the destination via the respective nodes.

Difference to Dijkstra’s Algorithm: Detours are Avoided

Here, the difference to Dijkstra’s algorithm becomes clear. With Dijkstra, we had sorted the table according to total costs, which is why node C (total cost 3.0) was sorted before node F (total cost 4.0).

Due to the heuristic component, node F (cost sum 5.5) is ahead of node C (cost sum 6.2) in the A* algorithm. The A* algorithm, therefore, considers it more likely to reach the destination faster via node F than via node C. If we take another look at the section of the map that the algorithm has considered so far, this makes sense:

Node F is located in the direction of the destination node H, while the path via node C leads in the wrong direction.

A* will soon realize that the detour via node C is ultimately faster. In general, however, detours are longer. Therefore, it is justified to prioritize them lower.

Step 2: Examining All Neighbors of Node E

We repeat the process for the node that is now at the top of the table. That is node E. We extract it and look at its neighbors, A, B, D, and F:

Node D is no longer contained in the table. That means that we have already discovered the shortest path to it (it is the start node we dealt with in the previous step). We can therefore ignore it at this point.

Nodes A and B have infinite total costs, i.e., we have not yet found a path to them. We calculate the total cost from the start to these nodes by adding the total cost to the current node E and the cost from node E to nodes A and B, respectively:

Node	Total cost calculation
Node A	1.0 (total cost from the start to E) + 3.0 (cost E–A) = 4.0
Node B	1.0 (total cost from the start to E) + 5.0 (cost E–B) = 6.0

We add the minimum remaining costs to the target calculated in advance to the respective total costs:

Node	Cost sum calculation
Node A	4.0 (total cost from the start to A) + 3.9 (minimum remaining cost from A to the target) = 7.9
Node B	6.0 (total cost from the start to B) + 4.3 (minimum remaining cost from B to the target) = 10.3

We update the entries in the graph:

A path has already been found to node F with a total cost of 4.0. The path via the current node E may be faster. To check this, we calculate the total cost via E for node F as well:

Node	Total cost calculation
Node F	1.0 (total cost from the start to E) + 6.0 (cost E–F) = 7.0

The total costs calculated via E (7.0) are higher than the previously stored total costs (4.0). That means: We could find a new way to F, but it is more expensive than the previously known one. Thus we ignore it, i.e., we leave the table entries for node F unchanged.

The table now looks like this (the changes are again marked in bold):

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
F	D	4.0	1.5	5.5
C	D	3.0	3.2	6.2
A	E	4.0	3.9	7.9
B	E	6.0	4.3	10.3
G	–	∞	2.8	∞
H	–	∞	0.0	∞
I	–	∞	1.6	∞

The new entries read like this: Nodes A and B have been discovered. They can be reached via node E in 4 and 6 minutes, respectively. Adding the minimum remaining costs to the destination results in 7.9 and 10.3 minutes, respectively, that it would take at least to reach the destination via the respective nodes. These values are higher than those of nodes F and C, so nodes A and B remain behind F and C in the table.

Step 3: Examining All Neighbors of Node F

We repeat the process for node F and examine its neighbors D, E, and H:

Nodes D and E are no longer in the table. We have already discovered the shortest paths to them (in the previous two steps).

So we only need to consider node H. We calculate, as before, the total cost from the start to node H:

Node	Total cost calculation
Node H	4.0 (total cost from the start to F) + 7.0 (cost F–H) = 11.0

Node H is the destination. Therefore, there are no remaining costs that we would have to add. We fill in the predecessor and the total costs:

We have thus found a path to the destination node H. It goes via node F and has a total cost of 11.0. We update node H in the table:

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
C	D	3.0	3.2	6.2
A	E	4.0	3.9	7.9
B	E	6.0	4.3	10.3
H	F	11.0	0.0	11.0
G	–	∞	2.8	∞
I	–	∞	1.6	∞

There are still three nodes in the table with a cost sum of less than 11.0, which means that we might find a faster way to the destination via these three nodes. We have to continue the process until the target node reaches the first position in the table.

Step 4: Examining All Neighbors of Node C

The next node in the table is node C. We extract it and examine its neighbors, A, D, and G:

Node D (our start node) is no longer in the table.

We calculate, as before, the total cost from the start via the current node C to nodes A and G:

Node	Total cost calculation
Node A	3.0 (total cost from the start to C) + 2.0 (cost C–A) = 5.0
Node G	3.0 (total cost from the start to C) + 2.0 (cost C–G) = 5.0

We had already discovered a path to node A via E with a total cost from the start of 4.0. The total cost via the new route to A is higher (5.0), so we ignore the newly discovered path.

We had not yet discovered a path to node G. We add to the just calculated total costs from the start the remaining costs to the destination calculated in advance:

Node	Cost sum calculation
Node G	5.0 (total cost from the start to G) + 2.8 (minimum remaining cost from G to the target) = 7.8

We enter predecessors and costs for node G in the graph:

And we update node G in the table:

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
G	C	5.0	2.8	7.8
A	E	4.0	3.9	7.9
B	E	6.0	4.3	10.3
H	F	11.0	0.0	11.0
I	–	∞	1.6	∞

Node G has moved up to first place in the table. The A* algorithm now assumes – with the heuristic’s help – that node G is the fastest way to the destination.

Step 5: Examining All Neighbors of Node G

So we take node G and examine its neighbors, C and H:

Node C is no longer in the table; we had completed it in the previous step.

We calculate the total cost from the start through node G to node H:

Node	Total cost calculation
Node H	5.0 (total cost from the start to G) + 4.0 (cost G–H) = 9.0

The cost currently stored in node H is 11.0. Thus, we have discovered a faster path to the destination node H via node G. We update predecessor and cost in node H:

There are no remaining costs in the target node.

The updated table looks like this:

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
A	E	4.0	3.9	7.9
H	G	9.0	0.0	9.0
B	E	6.0	4.3	10.3
I	–	∞	1.6	∞

Node A is still ahead of the destination node in the table. The sum of all costs in this node (7.9) is lower than the just calculated cost sum to node H. That means: If there were a beeline connection from node A to destination H, then the path via A would be faster than the just found path via G.

In the next step, the algorithm will find out whether there is such a path or not.

Step 6: Examining All Neighbors of Node A

Let’s go about it: We take node A and examine its neighbors, C and E:

Both nodes are no longer in the table. We have already processed both of them. So in this step, we will not find an undiscovered path to the target.

The table now looks like this:

Node	Predecessor	Total Cost From Start	Minimum Remaining Costs to Target	Sum of All Costs
H	G	9.0	0.0	9.0
B	E	6.0	4.3	10.3
I	–	∞	1.6	∞

Our target node has reached first place in the table.

Fastest Way to the Target Found

That means: There is no node via which we could find an even faster path to the destination.

Not even via node B?

The total cost from the start to node B is only 6.0, but with the minimum remaining cost of 4.3, the cost sum is at least 10.3, making it impossible to catch up with the current best value of 9.0.

Backtrace for Determining the Complete Path

We can see from the table: The destination node H can be reached fastest via node G. But how do we determine the entire path from the starting node D to the destination? To do this, we perform a so-called “backtrace”: We start at the destination node and follow all predecessor nodes until we reach the start node.

The easiest way to demonstrate this is with the graph:

The predecessor of the target node H is G; G’s predecessor is C; and the predecessor of C is the start node D. So the fastest path is: D–C–G–H.

Difference A* Algorithm to Dijkstra’s Algorithm

In the last step, the difference to Dijkstra’s algorithm became clear once again: Node B has lower total costs from the start (6.0) than node H (9.0). At this point, Dijkstra’s algorithm would still have to check whether we could reach the destination faster via node B.

Through the heuristic, the A* algorithm knows that a path via node B would cost at least 10.3 (cost from start 6.0 plus minimum remaining cost 4.3). Thus, the cost of the current path (9.0) is out of reach.

Thus, the A* algorithm found the fastest path to the destination in one less step than Dijkstra’s algorithm would have needed. The following diagram shows, for both algorithms, which nodes they processed until the target node H reached the top of the table – processed nodes have a dark blue border, the target node a light blue one:

Later, we will see that the difference will be much higher for more complex graphs (such as real road maps).

A* Algorithm – Informal Description

Preparation:

1. Create a table of all nodes with predecessors, the total cost from the start, the minimum remaining cost to the target, and the cost sum.
2. Set the total cost of the starting node to 0 and that of all other nodes to infinity.
3. Using the heuristic function, calculate the minimum remaining cost to the target for all nodes.

Processing the nodes:

As long as the table is not empty, take the element with the smallest cost sum and do the following with it:

• Is the extracted element the target node? If yes, the termination condition is fulfilled. Then, follow the predecessor nodes back to the start node to determine the fastest path.

• Otherwise, examine all neighbor nodes of the extracted element that are still in the table. For each neighbor node:

  1. Calculate the total cost from the start as the sum of the total cost from the start to the extracted node plus the cost from the extracted node to the examined neighbor node.

  2. Are the newly calculated total costs from the start lower than the previously stored ones? If no, then ignore this neighbor node. If yes, then:

     1. Calculate for the neighboring node the sum of the just calculated total cost from the start and the remaining cost to the destination.
     2. Enter the extracted node as the predecessor of the neighboring node.
     3. For the neighboring node, fill in the newly calculated total cost and the cost sum.

A* Algorithm – Java Source Code

In the following section, I will show you, step by step, how to implement the A* algorithm in Java and which data structures to use best.

You can find the code in the package eu.happycoders.pathfinding.astar in my GitHub repository.

Data Structure for Nodes: NodeWithXYCoordinates

First, we need a data structure that stores the X and Y coordinates for each node (class NodeWithXYCoordinates in the GitHub repository):

public class NodeWithXYCoordinates implements Comparable<NodeWithXYCoordinates> {
  private final String name;
  private final double x;
  private final double y;

  // Constructor, getters, equals(), hashCode(), compareTo()
}

The methods equals(), hashCode(), and compareTo(), which I haven’t printed here, are based on the name of the node.

Data Structure for the Graph: Guava ValueGraph

As data structure for the graph, we use the class ValueGraph of the Google Core Libraries for Java. The library provides various graph types, which are explained here. We are going to use a MutableValueGraph.

The following code shows how to create a graph that corresponds to the one from the example above. I manually took the X and Y coordinates from the graph with the coordinate system. The unit is meters; however, for finding the fastest path, the unit is actually irrelevant.

private static ValueGraph<NodeWithXYCoordinates, Double> createSampleGraph() {
  MutableValueGraph<NodeWithXYCoordinates, Double> graph =
      ValueGraphBuilder.undirected().build();

  NodeWithXYCoordinates a = new NodeWithXYCoordinates("A", 2_410, 6_230);
  NodeWithXYCoordinates b = new NodeWithXYCoordinates("B", 8_980, 6_080);
  NodeWithXYCoordinates c = new NodeWithXYCoordinates("C",   560, 3_360);
  NodeWithXYCoordinates d = new NodeWithXYCoordinates("D", 2_980, 3_900);
  NodeWithXYCoordinates e = new NodeWithXYCoordinates("E", 4_220, 4_280);
  NodeWithXYCoordinates f = new NodeWithXYCoordinates("F", 4_000, 2_600);
  NodeWithXYCoordinates g = new NodeWithXYCoordinates("G",     0,     0);
  NodeWithXYCoordinates h = new NodeWithXYCoordinates("H", 4_850,   110);
  NodeWithXYCoordinates i = new NodeWithXYCoordinates("I", 7_500,     0);

  graph.putEdgeValue(a, c, 2.0);
  graph.putEdgeValue(a, e, 3.0);
  graph.putEdgeValue(b, e, 5.0);
  graph.putEdgeValue(b, i, 15.0);
  graph.putEdgeValue(c, d, 3.0);
  graph.putEdgeValue(c, g, 2.0);
  graph.putEdgeValue(d, e, 1.0);
  graph.putEdgeValue(d, f, 4.0);
  graph.putEdgeValue(e, f, 6.0);
  graph.putEdgeValue(f, h, 7.0);
  graph.putEdgeValue(g, h, 4.0);
  graph.putEdgeValue(h, i, 3.0);

  return graph;
}

The type parameters of the ValueGraph are:

1. Type of the nodes: in the example, we use NodeWithXYCoordinates for the nodes along with their X and Y coordinates
2. Type of edge values: in the example, we use Double for the costs between two nodes

The graph is undirected; thus, it does not matter in which order we specify the nodes in the putEdgeValue() method.

Heuristic Function: HeuristicForNodesWithXYCoordinates

The heuristic function needs to calculate the minimum remaining cost to the destination for a given node. It is convenient to implement the Function interface (in the GitHub repository, you will find the HeuristicForNodesWithXYCoordinates class with additional comments and debug output):

public class HeuristicForNodesWithXYCoordinates
    implements Function<NodeWithXYCoordinates, Double> {
  private final double maxSpeed;
  private final NodeWithXYCoordinates target;

  public HeuristicForNodesWithXYCoordinates(
      ValueGraph<NodeWithXYCoordinates, Double> graph, NodeWithXYCoordinates target) {
    this.maxSpeed = calculateMaxSpeed(graph);
    this.target = target;
  }

  private static double calculateMaxSpeed(
      ValueGraph<NodeWithXYCoordinates, Double> graph) {
    return graph.edges().stream()
        .map(edge -> calculateSpeed(graph, edge))
        .max(Double::compare)
        .get();
  }

  private static double calculateSpeed(
      ValueGraph<NodeWithXYCoordinates, Double> graph,
      EndpointPair<NodeWithXYCoordinates> edge) {
    double euclideanDistance = calculateEuclideanDistance(edge.nodeU(), edge.nodeV());
    double cost = graph.edgeValue(edge).get();
    double speed = euclideanDistance / cost;
    return speed;
  }

  public static double calculateEuclideanDistance(
      NodeWithXYCoordinates source, NodeWithXYCoordinates target) {
    double distanceX = target.getX() - source.getX();
    double distanceY = target.getY() - source.getY();
    return Math.sqrt(distanceX * distanceX + distanceY * distanceY);
  }

  @Override
  public Double apply(NodeWithXYCoordinates node) {
    double euclideanDistance = calculateEuclideanDistance(node, target);
    double minimumCost = euclideanDistance / maxSpeed;
    return minimumCost;
  }
}

We pass the graph and the target node to the constructor. The calculateMaxSpeed() method calculates the speed for all edges and determines the maximum. Maximum speed and target node are stored in instance variables.

In the apply() method, the heuristic is applied to the specified node: The Euclidean distance to the destination node is calculated and divided by the maximum speed, resulting in the minimum remaining cost from the specified node to the destination.

Data Structure: Table Entries

We need a data structure for the table of nodes, in which we store for each node:

• Its predecessor
• The total cost from the start
• The minimum remaining cost to the target
• The cost sum

The following code shows the AStarNodeWrapper class implemented for this purpose:

public class AStarNodeWrapper<N extends Comparable<N>>
    implements Comparable<AStarNodeWrapper<N>> {
  private final N node;
  private AStarNodeWrapper<N> predecessor;
  private double totalCostFromStart;
  private final double minimumRemainingCostToTarget;
  private double costSum;

  public AStarNodeWrapper(
      N node,
      AStarNodeWrapper<N> predecessor,
      double totalCostFromStart,
      double minimumRemainingCostToTarget) {
    this.node = node;
    this.predecessor = predecessor;
    this.totalCostFromStart = totalCostFromStart;
    this.minimumRemainingCostToTarget = minimumRemainingCostToTarget;
    calculateCostSum();
  }

  private void calculateCostSum() {
    this.costSum = this.totalCostFromStart + this.minimumRemainingCostToTarget;
  }

  // getter for node
  // getters and setters for predecessor

  public void setTotalCostFromStart(double totalCostFromStart) {
    this.totalCostFromStart = totalCostFromStart;
    calculateCostSum();
  }

  // getter for totalCostFromStart

  @Override
  public int compareTo(AStarNodeWrapper<N> o) {
    int compare = Double.compare(this.costSum, o.costSum);
    if (compare == 0) {
      compare = node.compareTo(o.node);
    }
    return compare;
  }

  // equals(), hashCode()
}

The type parameter N stands for the type of nodes – in our example, this will be NodeWithXYCoordinates. The parameterization allows us to use other types as well, e.g., a node with longitude and latitude – or one with an additional Z coordinate.

In the constructor and in the method setTotalCostFromStart(), we call calculateCostSum() to calculate the sum of total cost from the start and minimum remaining cost to the target.

This sum is used in the compareTo() method to define the natural order of the wrapper class so that it is sorted by cost sum in ascending order. If the cost sum is the same, we compare the nodes themselves. NodeWithXYCoordinates would be sorted by node name.

Data Structure: TreeSet as Table

If you have read the article about Dijkstra’s algorithm, you know that the PriorityQueue often used in pathfinding tutorials is not the optimal data structure for this table if we remove entries with remove() and reinsert them. I will show why this is so – and how the PriorityQueue with lazy deletion does without remove() entirely – in the section on time complexity. Here, we use a TreeSet.

The TreeSet returns the smallest element with the pollFirst() method. Due to the natural ordering of the AStarNodeWrapper objects described above, this will always be the node with the lowest sum of total cost from the start and minimum remaining cost to the target.

TreeSet<AStarNodeWrapper<N>> queue = new TreeSet<>();

Data Structure: Lookup Map for Wrappers

In the further course, we need a map that delivers the corresponding wrapper for a graph node. For this, we use a HashMap:

Map<N, AStarNodeWrapper<N>> nodeWrappers = new HashMap<>();

Data Structure: Processed Nodes

To be able to check whether we have already processed a node, i.e., found the shortest path to it, we create a HashSet:

Set<N> shortestPathFound = new HashSet<>();

This optimization – never touching a node again once it has been extracted – is the reason why the heuristic must be consistent (see “Heuristic Function”): Only then is it certain, when a node is extracted, that no shorter path to it will be found anymore. With a heuristic that is admissible but not consistent, the algorithm would have to reopen a processed node as soon as it finds a shorter path to it.

Preparation: Filling the Table

Let’s move on to the preparatory step, filling the table.

At this point, we can make an optimization compared to the informal description of the algorithm. Instead of writing all nodes into the table, we first write only the start node. We add other nodes to the table only after we have found a path to them.

That kills three birds with one stone:

1. We save table entries for those nodes that cannot be reached from the starting point or only via such intermediate nodes whose cost sum is higher than the cost of an already found path (like node I in the example).
2. We do not need to apply the heuristic function to these nodes either.
3. When we recalculate the cost sum of a node already in the table, we have to remove the node from the table and reinsert it so that it is sorted to the correct position. We also save this extra effort if we insert the nodes only after discovering a path to them.

So we start by wrapping our start node in an AStarNodeWrapper – and insert it into the lookup map and table:

AStarNodeWrapper<N> sourceWrapper =
    new AStarNodeWrapper<>(source, null, 0.0, heuristic.apply(source));
nodeWrappers.put(source, sourceWrapper);
queue.add(sourceWrapper);

Iterating Over All Nodes

The following loop implements the step-by-step processing of the nodes (method findShortestPath() in the AStarWithTreeSet class):

while (!queue.isEmpty()) {
  AStarNodeWrapper<N> nodeWrapper = queue.pollFirst();
  N node = nodeWrapper.getNode();
  shortestPathFound.add(node);

  // Have we reached the target? --> Build and return the path
  if (node.equals(target)) {
    return buildPath(nodeWrapper);
  }

  // Iterate over all neighbors
  Set<N> neighbors = graph.adjacentNodes(node);
  for (N neighbor : neighbors) {
    // Ignore neighbor if shortest path already found
    if (shortestPathFound.contains(neighbor)) {
      continue;
    }

    // Calculate total cost from start to neighbor via current node
    double cost =
        graph.edgeValue(node, neighbor).orElseThrow(IllegalStateException::new);
    double totalCostFromStart = nodeWrapper.getTotalCostFromStart() + cost;

    // Neighbor not yet discovered?
    AStarNodeWrapper<N> neighborWrapper = nodeWrappers.get(neighbor);
    if (neighborWrapper == null) {
      neighborWrapper =
          new AStarNodeWrapper<>(
              neighbor, nodeWrapper, totalCostFromStart, heuristic.apply(neighbor));
      nodeWrappers.put(neighbor, neighborWrapper);
      queue.add(neighborWrapper);
    }

    // Neighbor discovered, but total cost via current node is lower?
    // --> Update costs and predecessor
    else if (totalCostFromStart < neighborWrapper.getTotalCostFromStart()) {
      // The position in the TreeSet won't change automatically;
      // we have to remove and reinsert the node.
      // Because TreeSet uses compareTo() to identity a node to remove,
      // we have to remove it *before* we change the cost!
      queue.remove(neighborWrapper);

      neighborWrapper.setTotalCostFromStart(totalCostFromStart);
      neighborWrapper.setPredecessor(nodeWrapper);

      queue.add(neighborWrapper);
    }
  }
}

// All nodes were visited but the target was not found
return null;

The loop extracts the node with the smallest cost sum using pollFirst(), marks it as processed, and terminates if it is the target node. For each neighbor that has not yet been processed, it calculates the total cost via the current node and then distinguishes two cases:

• No path to the neighbor is known yet (neighborWrapper == null): We create an AStarNodeWrapper – with the current node as predecessor and the remaining cost from the heuristic – and insert it into the lookup map and the table.
• A path to the neighbor is known, but the new one is cheaper: We remove the wrapper from the TreeSet before changing its total cost because the TreeSet finds it via compareTo(), i.e., via the cost sum. Then we set the new total cost and predecessor and reinsert the wrapper so that it is sorted to the correct position.

A more expensive path to an already discovered neighbor meets neither condition and is ignored.

Backtrace: Determining the Path From Source to Target

In the if block commented with “Have we reached the target?”, the method buildPath() is called. This method follows the predecessors from the target node back to the start node, adding all nodes to a list and returning the list in reverse order:

private static <N extends Comparable<N>> List<N> buildPath(
    AStarNodeWrapper<N> nodeWrapper) {
  List<N> path = new ArrayList<>();
  while (nodeWrapper != null) {
    path.add(nodeWrapper.getNode());
    nodeWrapper = nodeWrapper.getPredecessor();
  }
  Collections.reverse(path);
  return path;
}

You can find the complete findShortestPath() method in the AStarWithTreeSet class in the GitHub repository. You can invoke the method like this:

ValueGraph<NodeWithXYCoordinates, Double> graph = createSampleGraph();

Map<String, NodeWithXYCoordinates> nodeByName = createNodeByNameMap(graph);

Function<NodeWithXYCoordinates, Double> heuristic =
    new HeuristicForNodesWithXYCoordinates(graph, target);

List<NodeWithXYCoordinates> shortestPath =
    AStarWithTreeSet.findShortestPath(
        graph, nodeByName.get("D"), nodeByName.get("H"), heuristic);

You can find this and other examples in the TestWithSampleGraph class in the GitHub repository.

Let us now turn to time complexity.

Time Complexity of the A* Algorithm

To determine the A* algorithm’s time complexity, we look at the code block by block. We determine the partial complexities for each block and then add them together.

We denote the number of nodes of the graph by n and the number of edges by m.

We do not need to take into account the calculation of the maximum speed in the graph here. We can do the math once per graph, and then store the maximum speed as part of the graph data.

1. Inserting the start node into the table: The effort is independent of the graph’s size, so it is constant – O(1).
2. Extracting the nodes from the table: The complexity of removing the smallest element of the table depends on the data structure used – we denote it by T_em (“extract minimum”). Each node is extracted at most once, so the complexity is O(n · T_em).
3. Verifying whether we’ve already found the shortest path to a node: This check is performed for each node and all edges leading away from it. Since each edge connects two nodes, this happens at most twice per edge, i.e., 2m times. Since we use a set for the check, it is done in constant time; for 2m checks, the total effort is thus O(m).
4. Calculating the total cost from the start: The calculation is simple addition and has the complexity O(1). The calculation is done at most once per edge because we follow each edge at most once. The complexity is, therefore, also for this block O(m).
5. Accessing the wrappers: The lookup map for the AStarNodeWrapper objects is accessed once after we’ve calculated the total cost. The access cost is constant, so the complexity for this step is also O(m).
6. Calculating the heuristic: We can calculate the heuristic function in constant time. It is applied at most once per node. The complexity is, therefore, O(n).
7. Inserting into the table: The complexity of insertion – just like the complexity of extraction – depends on the data structure used. We denote it with T_i (“insert”). Each node is inserted at most once. The complexity is, therefore, O(n · T_i).
8. Updating the total costs and thus the cost sum in the table: This complexity also depends on the data structure. With the TreeSet, for example, we have to remove the node and reinsert it. Other data structures (you’ll learn about one in a moment) have an independent function for this. We generally refer to the time as T_dk (“decrease key”). The function is called at most as many times as we calculate the total cost from the start, therefore, at most m times. So the complexity for this block is O(m · T_dk).

We add up all partial complexities:

O(1) + O(n · T_em) + O(m) + O(m) + O(m) + O(n · T_i) + O(n) + O(m · T_dk)

We can neglect constant time O(1); likewise, O(m) is negligible with respect to O(m · T_dk), and O(n) is negligible with respect to O(n · T_em) and O(n · T_i). We can therefore shorten the term to O(n · T_em) + O(n · T_i) + O(m · T_dk) and then further summarize it to:

O(n · (T_em + T_i) + m · T_dk)

In the following sections, we’ll look at what the values for T_em, T_i, and T_dk are for the various data structures – and what overall complexities result.

A* Algorithm With TreeSet

The TreeSet used in the source code has the following complexities (these can be taken from the TreeSet documentation). For a better understanding, I specify the T values here with their full designation:

• Extracting the smallest entry with pollFirst(): T_{extractMinimum} = O(log n)
• Inserting an entry with add(): T_insert = O(log n)
• Reducing the cost with remove() and add(): T_decreaseKey = O(log n) + O(log n) = O(log n)

We substitute these values into the general formula from the previous section and arrive at:

O(n · log n + m · log n)

For the particular case where the number of edges is a multiple of the number of nodes – in big O notation: m ∈ O(n) – we can equate m and n in the computation of time complexity.

The formula then gets simplified to:

O(n · log n) – for m ∈ O(n)

The time is therefore quasilinear.

It should be noted that TreeSet violates the interface definition of the remove() method of the Collection and Set interfaces: It does not identify the element to be deleted using the equals() method but via the compareTo() method. Therefore, we must make sure that the compareTo() method of the node class used returns 0 if and only if the equals() method returns true.

Runtime With TreeSet

With the program TestAStarRuntime, we can measure how long the A* algorithm takes to find the shortest path between two nodes in graphs of different sizes. The program generates random graphs and then measures the execution time of AStarWithTreeSet.findShortestPath().

For each graph size, 100 tests are performed with different graphs, and finally, the median of the measured values is printed. I measured on an Apple M5 Pro with Java 27. The following diagram shows the runtime measurements in relation to the graph size for the TreeSet:

We can see the predicted quasilinear growth reasonably well.

A* Algorithm With PriorityQueue

When speaking about the data structure, I had already mentioned the frequently used PriorityQueue. Why is it not a smart choice if we use it the way we use the TreeSet – removing entries with remove() and reinserting them?

Again, we take the complexities directly from the PriorityQueue JavaDoc:

• Extracting the smallest entry with poll(): T_{extractMinimum} = O(log n)
• Inserting an entry with offer(): T_insert = O(log n)
• Reducing the cost with remove() and offer(): T_decreaseKey = O(n) + O(log n) = O(n)

The first two parameters, T_em and T_i, are identical to those of the TreeSet.

The third parameter, T_dk, is O(n) for PriorityQueue – in contrast to the much more favorable complexity class O(log n) for TreeSet.

What does this mean for the time complexity of the A* algorithm? We substitute the parameters into the general formula O(n · (T_em + T_i) + m · T_dk) and get:

O(n · (log n + log n) + m · n)

log n + log n is 2 · log n, and constants can be omitted. The term thus shortens to:

O(n · log n + m · n)

For the special case m ∈ O(n) (the number of edges is a multiple of the number of nodes), we can simplify the formula to O(n · log n + n²). Besides the quadratic part n², we can neglect the quasilinear part n · log n. What remains is:

O(n²) – for m ∈ O(n)

Thus, using a PriorityQueue with remove() leads to quadratic time, a much worse complexity class than quasilinear time.

Runtime With PriorityQueue

By replacing the AStarWithTreeSet class with AStarWithPriorityQueue (class in GitHub) in the runTestForGraphSize() method of TestAStarRuntime, we can measure runtimes using PriorityQueue.

The following diagram shows the measurement result next to that of the TreeSet:

This time, we can see the quadratic growth very well.

PriorityQueue Without remove(): Lazy Deletion

The PriorityQueue can also be used without the expensive remove() method. This variant is called lazy deletion; in the Dijkstra article, I show it with a listing and a measurement.

If we find a shorter path to an already discovered node, we do not remove its entry from the queue. Instead, we insert a second entry with the smaller cost sum – and skip the outdated entry when poll() returns it later. We recognize it by the fact that its node is already in the shortestPathFound set by then.

We insert at most one entry per edge, so the queue contains at most m entries. Inserting and extracting each cost O(log m). Since a graph has at most n² edges, log m ≤ 2 · log n, which gives us:

O(m · log n)

For m ∈ O(n), this is – as with the TreeSet – O(n · log n). In return, the queue grows: It contains up to m entries instead of at most n. With Dijkstra’s algorithm, this variant was faster in the measurement than both TreeSet and Fibonacci heap.

A* Algorithm With Fibonacci Heap

In theory, the Fibonacci heap is even better suited. Its operations have the following amortized runtimes:

• Extracting the smallest entry: T_{extractMinimum} = O(log n)
• Inserting an entry: T_insert = O(1)
• Reducing the cost: T_decreaseKey = O(1)

So here we have two parts with constant time. Let’s put the parameters into the general formula O(n · (T_em + T_i) + m · T_dk):

O(n · log n + m)

For the special case m ∈ O(n), the formula simplifies to:

O(n · log n) – for m ∈ O(n)

In terms of the time complexity of the overall algorithm, the Fibonacci heap gives us no advantage. What does the runtime look like in practice?

Runtime With Fibonacci Heap

Unfortunately, the JDK does not include a Fibonacci heap. Instead, I use the Fibonacci heap implementation by Keith Schwarz.

I did not copy this class and the corresponding A* implementation into my repository for copyright reasons. You can download the class at the given link and write an AStarWithFibonacciHeap yourself for practice.

Using the Fibonacci heap, I get the following measurements:

The A* algorithm is slightly faster with the Fibonacci heap than with the TreeSet – at 300,625 nodes, it takes 187 instead of 242 ms.

Time Complexity – Summary

The following table summarizes the time complexity of the A* algorithm depending on the data structure used:

Data structure	Tem	Ti	Tdk	Time complexity general	Time complexity for m ∈ O(n)
PriorityQueue	O(log n)	O(log n)	O(n)	O(n · log n + m · n)	O(n²)
TreeSet	O(log n)	O(log n)	O(log n)	O(n · log n + m · log n)	O(n · log n)
FibonacciHeap	O(log n)	O(1)	O(1)	O(n · log n + m)	O(n · log n)

The PriorityQueue with lazy deletion does not fit into this scheme because it inserts and extracts several entries for one node. Its time complexity is O(m · log n) – for m ∈ O(n), that is also O(n · log n).

Time Complexity A* Algorithm vs. Dijkstra’s Algorithm

The time complexity classes in A* are the same as in Dijkstra. But what about the running times?

For the comparison, I measured Dijkstra’s algorithm on the same graphs as A*. The A* code itself is all it takes: If the heuristic returns 0 for every node, the cost sum equals the total cost from the start – and A* processes the nodes in exactly the same order as Dijkstra. In the following diagram, the Dijkstra values are dashed, in the color of the respective data structure:

The runtimes are significantly better with the A* algorithm: From 50,000 nodes on, Dijkstra takes 2 to 3 times as long. However, this is not a generally valid statement. Whether and to what extent A* is faster than Dijkstra depends strongly on the graph’s structure. For street maps, A* is usually significantly faster.

In a labyrinth, where the fastest path often leads away from the destination, things can look quite different.

Summary and Outlook

This article has shown with an example, with an informal description, and with Java source code, how the A* algorithm works.

To determine the time complexity, we first developed a general Landau notation and then concretized it for the TreeSet, PriorityQueue, and Fibonacci heap data structures – and for the PriorityQueue with lazy deletion, which does without remove() entirely.

The time complexities correspond to those of Dijkstra’s algorithm; the running times are clearly better with A* than with Dijkstra. Thus, if we can define a heuristic function and the fastest path usually leads roughly in the goal’s direction, the A* algorithm is always preferable.

Preview: Bellman-Ford Algorithm

However, there are also situations where neither Dijkstra nor A* is suitable: Both require that no edge weight is negative. As soon as we extract a node from the table, the fastest path to it is considered found. That is only true if a detour via further edges can no longer reduce the total cost – but an edge with a negative weight could.

How can negative edge weights exist in reality (and not only in a constructed mathematical model)? And how to solve the shortest path problem in such a case? That’s what you will learn in the next article about the Bellman-Ford algorithm.