Breadth-first search from the top-left to the bottom-right. Every reached cell gets g, its distance so far. The frontier is expanded first-in first-out, so the search grows in rings of equal distance in every direction, walls permitting.
Breadth-first search on a 5 by 6 grid.
Expand (0,0), g = 0. New neighbours (1,0), (0,1) get g = 1. Frontier: 2.
Expand (0,0), 2 new cells.
Expand (1,0), g = 1. New neighbours (2,0) get g = 2. Frontier: 2.
Expand (1,0), 1 new cells.
Expand (0,1), g = 1. New neighbours (0,2) get g = 2. Frontier: 2.
Expand (0,1), 1 new cells.
Expand (2,0), g = 2. New neighbours (2,1) get g = 3. Frontier: 2.
Expand (2,0), 1 new cells.
Expand (0,2), g = 2. New neighbours (0,3) get g = 3. Frontier: 2.
Expand (0,2), 1 new cells.
Expand (2,1), g = 3. New neighbours (2,2) get g = 4. Frontier: 2.
Expand (2,1), 1 new cells.
Expand (0,3), g = 3. New neighbours (0,4) get g = 4. Frontier: 2.
Expand (0,3), 1 new cells.
Expand (2,2), g = 4. New neighbours (3,2) get g = 5. Frontier: 2.
Expand (2,2), 1 new cells.
Expand (0,4), g = 4. New neighbours (1,4), (0,5) get g = 5. Frontier: 3.
Expand (0,4), 2 new cells.
Expand (3,2), g = 5. New neighbours (4,2) get g = 6. Frontier: 3.
Expand (3,2), 1 new cells.
Expand (1,4), g = 5. New neighbours (2,4), (1,5) get g = 6. Frontier: 4.
Expand (1,4), 2 new cells.
Expand (0,5), g = 5. Every open neighbour was reached already, so nothing joins the frontier.
Expand (0,5), 0 new cells.
Expand (4,2), g = 6. New neighbours (4,3), (4,1) get g = 7. Frontier: 4.
Expand (4,2), 2 new cells.
Expand (2,4), g = 6. New neighbours (3,4), (2,5) get g = 7. Frontier: 5.
Expand (2,4), 2 new cells.
Expand (1,5), g = 6. Every open neighbour was reached already, so nothing joins the frontier.
Expand (1,5), 0 new cells.
Expand (4,3), g = 7. New neighbours (4,4) get g = 8. Frontier: 4.
Expand (4,3), 1 new cells.
Expand (4,1), g = 7. New neighbours (4,0) get g = 8. Frontier: 4.
Expand (4,1), 1 new cells.
Expand (3,4), g = 7. New neighbours (3,5) get g = 8. Frontier: 4.
Expand (3,4), 1 new cells.
Expand (2,5), g = 7. Every open neighbour was reached already, so nothing joins the frontier.
Expand (2,5), 0 new cells.
Expand (4,4), g = 8. New neighbours (4,5) get g = 9. Frontier: 3.
Expand (4,4), 1 new cells.
Expand (4,0), g = 8. Every open neighbour was reached already, so nothing joins the frontier.
Expand (4,0), 0 new cells.
Expand (3,5), g = 8. 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. Every cell at a smaller distance was expanded before it, so this distance is the shortest.
Goal reached at distance 9.
Shortest path of 9 steps after expanding 23 of the 23 open cells. BFS explored in every direction, so it looked at cells no shortest path uses.
Path of 9 steps.