The A* path-finding algorithm

g, h and f

For each vertex n, A* keeps:

• g(n): the actual cost of the best path found so far from the start to n;
• h(n): a heuristic estimate of the cost from n to the goal (for example the straight-line distance on a map);
• f(n) = g(n) + h(n): the estimated total cost of a path through n.

A* always expands the open vertex with the lowest f.

The algorithm

1. Put the start in the open list with g = 0, f = h(start).

2. Take the open vertex with the lowest f; move it to the closed list. If it is the goal, stop.

3. For each neighbour not closed: g via current = g(current) + edge weight. If this is better than its recorded g (or it is new), record g, f = g + h and the previous vertex, and put it in the open list.

4. Repeat. Trace the path back using the previous vertices.

If the heuristic never overestimates the true remaining cost (it is admissible), A* is guaranteed to find a shortest path. With h = 0 everywhere, A* behaves exactly like Dijkstra.

Trace

Edges: S-A 3, S-B 3, A-C 4, B-C 2, B-D 5, C-G 4, D-G 2. Heuristic h: S 7, A 7, B 5, C 4, D 2, G 0.

Path S -> B -> C -> G, cost 9. A was never expanded.

A* compared with Dijkstra

Both always expand the most promising open vertex first; the heuristic is the difference.

Worked example

Explain why A* never expanded vertex A in the trace.

1. A's f = 3 + 7 = 10.
2. The goal G was reached with f = 9 before any vertex with f = 10 needed expanding.
3. The heuristic showed A was unlikely to lie on a shorter path.

Answer: Its f value (10) was never the lowest in the open list before the goal was found.

Check yourself

1. A vertex has g = 12 and h = 7. What is its f value?
   Show answer

   19. f = g + h = 19.

2. In the trace graph, what is the cost of the path A* finds from S to G?
   Show answer

   9. S -> B -> C -> G = 3 + 2 + 4 = 9.

3. In the trace, what f value does D get when it is first added to the open list?
   Show answer

   10. g(D) = g(B) + 5 = 8; f = 8 + 2 = 10.

4. How many vertices are moved to the closed list in the trace, including the goal?
   Show answer

   4. S, B, C, G.

5. What makes a heuristic admissible?
   • It always overestimates the cost
   • It is the same for every vertex
   • It is calculated after the path is found
   • It never overestimates the true cost to the goal
   Show answer

   It never overestimates the true cost to the goal. Admissibility guarantees A* returns a shortest path.

6. What happens if A* uses h = 0 for every vertex?
   • It never finds a path
   • It behaves like Dijkstra's algorithm
   • It always finds the longest path
   • It visits only the goal
   Show answer

   It behaves like Dijkstra's algorithm. f = g, so it chooses by distance from the start alone.

7. What is the main advantage of A* over Dijkstra's algorithm for finding a route to one destination?
   • It works with negative edge weights
   • It finds shortest paths to every vertex
   • It needs no edge weights
   • The heuristic guides it towards the goal, so it usually explores fewer vertices
   Show answer

   The heuristic guides it towards the goal, so it usually explores fewer vertices. Focus saves work on large maps.

8. Which is a suitable heuristic for A* on a road map?
   • The number of letters in each town's name
   • The longest road leaving each junction
   • The straight-line distance from each junction to the destination
   • A random number for each junction
   Show answer

   The straight-line distance from each junction to the destination. Straight-line distance never exceeds road distance, so it is admissible.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.