A* from the top-left to the bottom-right. Every reached cell gets g, its distance so far, and the frontier is expanded in order of f = g + h, where h is the Manhattan distance to the goal ignoring walls. h never overestimates, so the first time the goal is expanded its path is shortest.
A star search on a 5 by 6 grid.
Expand (0,0), g = 0, f = 9. New neighbours (1,0), (0,1) get g = 1 and f = 9, 9. Frontier: 2.
Expand (0,0), 2 new cells.
Expand (1,0), g = 1, f = 9. New neighbours (2,0) get g = 2 and f = 9. Frontier: 2.
Expand (1,0), 1 new cells.
Expand (0,1), g = 1, f = 9. New neighbours (0,2) get g = 2 and f = 9. Frontier: 2.
Expand (0,1), 1 new cells.
Expand (2,0), g = 2, f = 9. New neighbours (2,1) get g = 3 and f = 9. Frontier: 2.
Expand (2,0), 1 new cells.
Expand (0,2), g = 2, f = 9. New neighbours (0,3) get g = 3 and f = 9. Frontier: 2.
Expand (0,2), 1 new cells.
Expand (2,1), g = 3, f = 9. New neighbours (2,2) get g = 4 and f = 9. Frontier: 2.
Expand (2,1), 1 new cells.
Expand (0,3), g = 3, f = 9. New neighbours (0,4) get g = 4 and f = 9. Frontier: 2.
Expand (0,3), 1 new cells.
Expand (2,2), g = 4, f = 9. New neighbours (3,2) get g = 5 and f = 9. Frontier: 2.
Expand (2,2), 1 new cells.
Expand (0,4), g = 4, f = 9. New neighbours (1,4), (0,5) get g = 5 and f = 9, 9. Frontier: 3.
Expand (0,4), 2 new cells.
Expand (3,2), g = 5, f = 9. New neighbours (4,2) get g = 6 and f = 9. Frontier: 3.
Expand (3,2), 1 new cells.
Expand (1,4), g = 5, f = 9. New neighbours (2,4), (1,5) get g = 6 and f = 9, 9. Frontier: 4.
Expand (1,4), 2 new cells.
Expand (0,5), g = 5, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (0,5), 0 new cells.
Expand (4,2), g = 6, f = 9. New neighbours (4,3), (4,1) get g = 7 and f = 9, 11. Frontier: 4.
Expand (4,2), 2 new cells.
Expand (2,4), g = 6, f = 9. New neighbours (3,4), (2,5) get g = 7 and f = 9, 9. Frontier: 5.
Expand (2,4), 2 new cells.
Expand (1,5), g = 6, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (1,5), 0 new cells.
Expand (4,3), g = 7, f = 9. New neighbours (4,4) get g = 8 and f = 9. Frontier: 4.
Expand (4,3), 1 new cells.
Expand (3,4), g = 7, f = 9. New neighbours (3,5) get g = 8 and f = 9. Frontier: 4.
Expand (3,4), 1 new cells.
Expand (2,5), g = 7, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (2,5), 0 new cells.
Expand (4,4), g = 8, f = 9. New neighbours (4,5) get g = 9 and f = 9. Frontier: 3.
Expand (4,4), 1 new cells.
Expand (3,5), g = 8, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (3,5), 0 new cells.
The goal comes off the frontier with g = 9. Nothing left on the frontier has a smaller f, and f never overestimates, so no shorter path exists.
Goal reached at distance 9.
Shortest path of 9 steps after expanding 21 of the 23 open cells. The heuristic pulled the search toward the goal, so cells leading away were left alone.
Path of 9 steps.