35.08Intermediate / Advanced5 topics18 min5 interactive animations

A* and heuristics

A* is Dijkstra guided by a heuristic that estimates the distance to the goal: with an admissible (never too high) heuristic it still finds a shortest path, usually after expanding far fewer vertices.

Learning goals

Order the queue by f = g + h and explain what each term means
Define admissible and consistent heuristics and test them
Choose Manhattan, Euclidean or Chebyshev distance for a grid
Keep open and closed sets and count expanded cells

Prerequisites

Dijkstra's algorithmGrid BFS

Dijkstra spreads out like a ripple in every direction. If you know roughly where the goal is, you can aim: A* spends its effort on vertices that look like they lie on the way, which is why games and map software use it.

35.08.1

Admissible heuristics

A* orders the open vertices by f(v) = g(v) + h(v): the cost g found so far plus a heuristic guess h of the cost still to go. A heuristic is **admissible** if it never overestimates the true remaining cost: h(v) <= dist(v, goal) for every v. With an admissible heuristic the first time the goal is popped, its path is a shortest one.

With h = 0 A* is Dijkstra. The closer h is to the real distance (without exceeding it), the fewer vertices are expanded. The last option in the animation overestimates on purpose; its preset returns a longer path than the Manhattan one on the same grid.

Java

1static boolean isAdmissible(int n, int[][] edges, int[] h, int goal) {   // h[v] <= the true distance from v to goal; weights >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] d = new long[n];                                            // distances TO the goal: relax every edge backwards
4    Arrays.fill(d, INF);
5    d[goal] = 0;
6    for (int round = 0; round < n; round++)
7        for (int[] e : edges)
8            if (d[e[1]] != INF && d[e[1]] + e[2] < d[e[0]]) d[e[0]] = d[e[1]] + e[2];
9    for (int v = 0; v < n; v++)
10        if (d[v] != INF && h[v] > d[v]) return false;
11    return true;
12}

A* on a grid: open and closed sets, heuristics and admissibility

Interactive · edit the input

grid · 5 × 5

01234

▇

·G

Cell being expandedOpen setClosed set (g shown)Final pathWall

open set (smallest f first)

(0,0) f=8

Setup

A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.

Step 1 / 10

Java

1int astar(boolean[][] open, int sr, int sc, int tr, int tc) {   // fewest moves, or -1
2    int R = open.length, C = open[0].length;
3    int[][] g = new int[R][C];
4    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
5    g[sr][sc] = 0;
6    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);   // f = g + h, ties: larger g
7    pq.add(new int[]{heuristic(sr, sc, tr, tc), 0, sr, sc});
8    while (!pq.isEmpty()) {
9        int[] top = pq.poll(); int r = top[2], c = top[3];
10        if (top[1] > g[r][c]) continue;           // outdated entry
11        if (r == tr && c == tc) return g[r][c];   // the goal is popped with the smallest f: optimal if h never overestimates
12        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
13            int nr = r + d[0], nc = c + d[1];
14            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc]) continue;
15            if (g[r][c] + 1 >= g[nr][nc]) continue;
16            g[nr][nc] = g[r][c] + 1;
17            pq.add(new int[]{g[nr][nc] + heuristic(nr, nc, tr, tc), g[nr][nc], nr, nc});
18        }
19    }
20    return -1;
21}
22int heuristic(int r, int c, int tr, int tc) { return Math.abs(r - tr) + Math.abs(c - tc); }   // Manhattan

Live state

0 cells expanded1 cells opened

start

(0,0)

goal

(4,4)

h = Manhattan distance to the goal

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L5	start=(0,0) goal=(4,4) h=h = Manhattan distance to the goal	A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.
2	L15	cell=(0,0) g=0 f=8	Expand (0,0) with g = 0, f = 8. New or improved open cells: (1,0) f=8, (0,1) f=8.
3	L15	cell=(1,0) g=1 f=8	Expand (1,0) with g = 1, f = 8. New or improved open cells: (2,0) f=8.
4	L15	cell=(2,0) g=2 f=8	Expand (2,0) with g = 2, f = 8. New or improved open cells: (3,0) f=8, (2,1) f=8.
5	L15	cell=(3,0) g=3 f=8	Expand (3,0) with g = 3, f = 8. New or improved open cells: (4,0) f=8, (3,1) f=8.
6	L15	cell=(4,0) g=4 f=8	Expand (4,0) with g = 4, f = 8. New or improved open cells: (4,1) f=8.
7	L15	cell=(4,1) g=5 f=8	Expand (4,1) with g = 5, f = 8. New or improved open cells: (4,2) f=8.
8	L15	cell=(4,2) g=6 f=8	Expand (4,2) with g = 6, f = 8. New or improved open cells: (3,2) f=10, (4,3) f=8.
9	L15	cell=(4,3) g=7 f=8	Expand (4,3) with g = 7, f = 8. New or improved open cells: (3,3) f=10, (4,4) f=8.
10	L10	return=8 expanded=9 opened=14	The goal is the smallest f in the open set: path length 8, found after expanding 9 cells (14 opened). The heuristic never overestimates, so no shorter path exists.

35.08.2

Consistency

A heuristic is **consistent** (monotone) if for every edge u → v of weight w, h(u) <= w + h(v), and h(goal) = 0. It is the triangle inequality for estimates. Every consistent heuristic is admissible, but not the other way round.

With a consistent heuristic the f values along any path never decrease, so once a vertex is expanded its g is final and it never needs to be opened again: the closed set is safe. With an admissible but inconsistent heuristic, a vertex may have to be reopened.

Java

1static boolean isConsistent(int[][] edges, int[] h, int goal) {          // h[u] <= w + h[v] for every edge, and h[goal] == 0
2    if (h[goal] != 0) return false;
3    for (int[] e : edges)
4        if (h[e[0]] > e[2] + h[e[1]]) return false;
5    return true;
6}

A* on a grid: open and closed sets, heuristics and admissibility

Interactive · edit the input

grid · 5 × 5

01234

▇

·G

Cell being expandedOpen setClosed set (g shown)Final pathWall

open set (smallest f first)

(0,0) f=8

Setup

A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.

Step 1 / 10

Java

1int astar(boolean[][] open, int sr, int sc, int tr, int tc) {   // fewest moves, or -1
2    int R = open.length, C = open[0].length;
3    int[][] g = new int[R][C];
4    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
5    g[sr][sc] = 0;
6    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);   // f = g + h, ties: larger g
7    pq.add(new int[]{heuristic(sr, sc, tr, tc), 0, sr, sc});
8    while (!pq.isEmpty()) {
9        int[] top = pq.poll(); int r = top[2], c = top[3];
10        if (top[1] > g[r][c]) continue;           // outdated entry
11        if (r == tr && c == tc) return g[r][c];   // the goal is popped with the smallest f: optimal if h never overestimates
12        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
13            int nr = r + d[0], nc = c + d[1];
14            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc]) continue;
15            if (g[r][c] + 1 >= g[nr][nc]) continue;
16            g[nr][nc] = g[r][c] + 1;
17            pq.add(new int[]{g[nr][nc] + heuristic(nr, nc, tr, tc), g[nr][nc], nr, nc});
18        }
19    }
20    return -1;
21}
22int heuristic(int r, int c, int tr, int tc) { return Math.abs(r - tr) + Math.abs(c - tc); }   // Manhattan

Live state

0 cells expanded1 cells opened

start

(0,0)

goal

(4,4)

h = Manhattan distance to the goal

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L5	start=(0,0) goal=(4,4) h=h = Manhattan distance to the goal	A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.
2	L15	cell=(0,0) g=0 f=8	Expand (0,0) with g = 0, f = 8. New or improved open cells: (1,0) f=8, (0,1) f=8.
3	L15	cell=(1,0) g=1 f=8	Expand (1,0) with g = 1, f = 8. New or improved open cells: (2,0) f=8.
4	L15	cell=(2,0) g=2 f=8	Expand (2,0) with g = 2, f = 8. New or improved open cells: (3,0) f=8, (2,1) f=8.
5	L15	cell=(3,0) g=3 f=8	Expand (3,0) with g = 3, f = 8. New or improved open cells: (4,0) f=8, (3,1) f=8.
6	L15	cell=(4,0) g=4 f=8	Expand (4,0) with g = 4, f = 8. New or improved open cells: (4,1) f=8.
7	L15	cell=(4,1) g=5 f=8	Expand (4,1) with g = 5, f = 8. New or improved open cells: (4,2) f=8.
8	L15	cell=(4,2) g=6 f=8	Expand (4,2) with g = 6, f = 8. New or improved open cells: (3,2) f=10, (4,3) f=8.
9	L15	cell=(4,3) g=7 f=8	Expand (4,3) with g = 7, f = 8. New or improved open cells: (3,3) f=10, (4,4) f=8.
10	L10	return=8 expanded=9 opened=14	The goal is the smallest f in the open set: path length 8, found after expanding 9 cells (14 opened). The heuristic never overestimates, so no shorter path exists.

35.08.3

Euclidean/Manhattan heuristics

On a grid the right heuristic depends on the moves. With **4 directions** and unit cost the true distance in an empty grid is the **Manhattan** distance |dr| + |dc|, which is admissible and the best simple guess. With **8 directions** and unit-cost diagonals, the true distance is the **Chebyshev** distance max(|dr|, |dc|).

**Euclidean** distance sqrt(dr² + dc²) is admissible for 4 directions (it is smaller than Manhattan) but weaker, so more cells are expanded; the animation's third option shows that. It overestimates when diagonal moves cost 1, so use Chebyshev there.

Java

1static int manhattan(int r, int c, int tr, int tc) { return Math.abs(r - tr) + Math.abs(c - tc); }          // 4 directions
2static int chebyshev(int r, int c, int tr, int tc) { return Math.max(Math.abs(r - tr), Math.abs(c - tc)); }   // 8 directions, diagonal cost 1
3static double euclidean(int r, int c, int tr, int tc) { return Math.hypot(r - tr, c - tc); }               // admissible for 4 directions, weaker

A* on a grid: open and closed sets, heuristics and admissibility

Interactive · edit the input

grid · 5 × 5

01234

▇

·G

Cell being expandedOpen setClosed set (g shown)Final pathWall

open set (smallest f first)

(0,0) f=8

Setup

A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.

Step 1 / 10

Java

1int astar(boolean[][] open, int sr, int sc, int tr, int tc) {   // fewest moves, or -1
2    int R = open.length, C = open[0].length;
3    int[][] g = new int[R][C];
4    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
5    g[sr][sc] = 0;
6    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);   // f = g + h, ties: larger g
7    pq.add(new int[]{heuristic(sr, sc, tr, tc), 0, sr, sc});
8    while (!pq.isEmpty()) {
9        int[] top = pq.poll(); int r = top[2], c = top[3];
10        if (top[1] > g[r][c]) continue;           // outdated entry
11        if (r == tr && c == tc) return g[r][c];   // the goal is popped with the smallest f: optimal if h never overestimates
12        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
13            int nr = r + d[0], nc = c + d[1];
14            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc]) continue;
15            if (g[r][c] + 1 >= g[nr][nc]) continue;
16            g[nr][nc] = g[r][c] + 1;
17            pq.add(new int[]{g[nr][nc] + heuristic(nr, nc, tr, tc), g[nr][nc], nr, nc});
18        }
19    }
20    return -1;
21}
22int heuristic(int r, int c, int tr, int tc) { return Math.abs(r - tr) + Math.abs(c - tc); }   // Manhattan

Live state

0 cells expanded1 cells opened

start

(0,0)

goal

(4,4)

h = Manhattan distance to the goal

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L5	start=(0,0) goal=(4,4) h=h = Manhattan distance to the goal	A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.
2	L15	cell=(0,0) g=0 f=8	Expand (0,0) with g = 0, f = 8. New or improved open cells: (1,0) f=8, (0,1) f=8.
3	L15	cell=(1,0) g=1 f=8	Expand (1,0) with g = 1, f = 8. New or improved open cells: (2,0) f=8.
4	L15	cell=(2,0) g=2 f=8	Expand (2,0) with g = 2, f = 8. New or improved open cells: (3,0) f=8, (2,1) f=8.
5	L15	cell=(3,0) g=3 f=8	Expand (3,0) with g = 3, f = 8. New or improved open cells: (4,0) f=8, (3,1) f=8.
6	L15	cell=(4,0) g=4 f=8	Expand (4,0) with g = 4, f = 8. New or improved open cells: (4,1) f=8.
7	L15	cell=(4,1) g=5 f=8	Expand (4,1) with g = 5, f = 8. New or improved open cells: (4,2) f=8.
8	L15	cell=(4,2) g=6 f=8	Expand (4,2) with g = 6, f = 8. New or improved open cells: (3,2) f=10, (4,3) f=8.
9	L15	cell=(4,3) g=7 f=8	Expand (4,3) with g = 7, f = 8. New or improved open cells: (3,3) f=10, (4,4) f=8.
10	L10	return=8 expanded=9 opened=14	The goal is the smallest f in the open set: path length 8, found after expanding 9 cells (14 opened). The heuristic never overestimates, so no shorter path exists.

35.08.4

Open/closed sets

The **open set** holds discovered cells that have not been expanded, in a priority queue by f. The **closed set** holds cells already expanded. Each round, pop the open cell with the smallest f, mark it closed, and for each open neighbour set g (if better) and push it. Stop when the goal is popped.

The animation colours the open set and the closed set differently and shows g in each cell; the preset results tell how many cells were expanded and opened. The function below returns those counts with Manhattan distance, using stale-entry skipping in place of a decrease-key.

Java

1static int[] astarStats(boolean[][] open, int sr, int sc, int tr, int tc) {   // {path length or -1, cells expanded, cells opened}
2    int R = open.length, C = open[0].length;
3    int[][] g = new int[R][C];
4    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
5    boolean[][] closed = new boolean[R][C];
6    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);   // {f, g, r, c}; ties: larger g
7    g[sr][sc] = 0;
8    pq.add(new int[]{Math.abs(sr - tr) + Math.abs(sc - tc), 0, sr, sc});
9    int expanded = 0, opened = 1;
10    while (!pq.isEmpty()) {
11        int[] top = pq.poll();
12        int r = top[2], c = top[3];
13        if (closed[r][c]) continue;                                       // already expanded (the heuristic is consistent)
14        closed[r][c] = true;
15        expanded++;
16        if (r == tr && c == tc) return new int[]{g[r][c], expanded, opened};
17        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
18            int nr = r + d[0], nc = c + d[1];
19            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc] || closed[nr][nc]) continue;
20            if (g[r][c] + 1 >= g[nr][nc]) continue;
21            g[nr][nc] = g[r][c] + 1;
22            opened++;
23            pq.add(new int[]{g[nr][nc] + Math.abs(nr - tr) + Math.abs(nc - tc), g[nr][nc], nr, nc});
24        }
25    }
26    return new int[]{-1, expanded, opened};
27}

A* on a grid: open and closed sets, heuristics and admissibility

Interactive · edit the input

grid · 5 × 5

01234

▇

·G

Cell being expandedOpen setClosed set (g shown)Final pathWall

open set (smallest f first)

(0,0) f=8

Setup

A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.

Step 1 / 10

Java

1int astar(boolean[][] open, int sr, int sc, int tr, int tc) {   // fewest moves, or -1
2    int R = open.length, C = open[0].length;
3    int[][] g = new int[R][C];
4    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
5    g[sr][sc] = 0;
6    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);   // f = g + h, ties: larger g
7    pq.add(new int[]{heuristic(sr, sc, tr, tc), 0, sr, sc});
8    while (!pq.isEmpty()) {
9        int[] top = pq.poll(); int r = top[2], c = top[3];
10        if (top[1] > g[r][c]) continue;           // outdated entry
11        if (r == tr && c == tc) return g[r][c];   // the goal is popped with the smallest f: optimal if h never overestimates
12        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
13            int nr = r + d[0], nc = c + d[1];
14            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc]) continue;
15            if (g[r][c] + 1 >= g[nr][nc]) continue;
16            g[nr][nc] = g[r][c] + 1;
17            pq.add(new int[]{g[nr][nc] + heuristic(nr, nc, tr, tc), g[nr][nc], nr, nc});
18        }
19    }
20    return -1;
21}
22int heuristic(int r, int c, int tr, int tc) { return Math.abs(r - tr) + Math.abs(c - tc); }   // Manhattan

Live state

0 cells expanded1 cells opened

start

(0,0)

goal

(4,4)

h = Manhattan distance to the goal

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L5	start=(0,0) goal=(4,4) h=h = Manhattan distance to the goal	A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.
2	L15	cell=(0,0) g=0 f=8	Expand (0,0) with g = 0, f = 8. New or improved open cells: (1,0) f=8, (0,1) f=8.
3	L15	cell=(1,0) g=1 f=8	Expand (1,0) with g = 1, f = 8. New or improved open cells: (2,0) f=8.
4	L15	cell=(2,0) g=2 f=8	Expand (2,0) with g = 2, f = 8. New or improved open cells: (3,0) f=8, (2,1) f=8.
5	L15	cell=(3,0) g=3 f=8	Expand (3,0) with g = 3, f = 8. New or improved open cells: (4,0) f=8, (3,1) f=8.
6	L15	cell=(4,0) g=4 f=8	Expand (4,0) with g = 4, f = 8. New or improved open cells: (4,1) f=8.
7	L15	cell=(4,1) g=5 f=8	Expand (4,1) with g = 5, f = 8. New or improved open cells: (4,2) f=8.
8	L15	cell=(4,2) g=6 f=8	Expand (4,2) with g = 6, f = 8. New or improved open cells: (3,2) f=10, (4,3) f=8.
9	L15	cell=(4,3) g=7 f=8	Expand (4,3) with g = 7, f = 8. New or improved open cells: (3,3) f=10, (4,4) f=8.
10	L10	return=8 expanded=9 opened=14	The goal is the smallest f in the open set: path length 8, found after expanding 9 cells (14 opened). The heuristic never overestimates, so no shorter path exists.

35.08.5

Grid search

Putting it together on a grid: the start and goal are cells, the moves are the four (or eight) neighbours, walls are not entered, each move costs 1, and the heuristic is Manhattan (or Chebyshev for eight directions). The result is the length of a shortest path, or -1 if there is none.

Without a wall A* walks nearly straight to the goal. Walls that form a pocket in front of the goal are the hard case: A* first fills the pocket, because every cell in it looks close to the goal. Compare the first two presets: the same grid with Manhattan and with no heuristic.

Java

1static int astarGrid(boolean[][] open, int sr, int sc, int tr, int tc, boolean diagonals) {   // fewest moves, or -1
2    int R = open.length, C = open[0].length;
3    int[][] dirs = diagonals ? new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
4                             : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
5    int[][] g = new int[R][C];
6    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
7    g[sr][sc] = 0;
8    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
9    pq.add(new int[]{h(sr, sc, tr, tc, diagonals), 0, sr, sc});
10    while (!pq.isEmpty()) {
11        int[] top = pq.poll();
12        int r = top[2], c = top[3];
13        if (top[1] > g[r][c]) continue;                                    // outdated entry
14        if (r == tr && c == tc) return g[r][c];
15        for (int[] d : dirs) {
16            int nr = r + d[0], nc = c + d[1];
17            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc]) continue;
18            if (g[r][c] + 1 >= g[nr][nc]) continue;
19            g[nr][nc] = g[r][c] + 1;
20            pq.add(new int[]{g[nr][nc] + h(nr, nc, tr, tc, diagonals), g[nr][nc], nr, nc});
21        }
22    }
23    return -1;
24}
25static int h(int r, int c, int tr, int tc, boolean diagonals) {           // Chebyshev with diagonals, Manhattan without
26    int dr = Math.abs(r - tr), dc = Math.abs(c - tc);
27    return diagonals ? Math.max(dr, dc) : dr + dc;
28}

A* on a grid: open and closed sets, heuristics and admissibility

Interactive · edit the input

grid · 5 × 5

01234

▇

·G

Cell being expandedOpen setClosed set (g shown)Final pathWall

open set (smallest f first)

(0,0) f=8

Setup

A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.

Step 1 / 10

Java

1int astar(boolean[][] open, int sr, int sc, int tr, int tc) {   // fewest moves, or -1
2    int R = open.length, C = open[0].length;
3    int[][] g = new int[R][C];
4    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
5    g[sr][sc] = 0;
6    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);   // f = g + h, ties: larger g
7    pq.add(new int[]{heuristic(sr, sc, tr, tc), 0, sr, sc});
8    while (!pq.isEmpty()) {
9        int[] top = pq.poll(); int r = top[2], c = top[3];
10        if (top[1] > g[r][c]) continue;           // outdated entry
11        if (r == tr && c == tc) return g[r][c];   // the goal is popped with the smallest f: optimal if h never overestimates
12        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
13            int nr = r + d[0], nc = c + d[1];
14            if (nr < 0 || nr >= R || nc < 0 || nc >= C || !open[nr][nc]) continue;
15            if (g[r][c] + 1 >= g[nr][nc]) continue;
16            g[nr][nc] = g[r][c] + 1;
17            pq.add(new int[]{g[nr][nc] + heuristic(nr, nc, tr, tc), g[nr][nc], nr, nc});
18        }
19    }
20    return -1;
21}
22int heuristic(int r, int c, int tr, int tc) { return Math.abs(r - tr) + Math.abs(c - tc); }   // Manhattan

Live state

0 cells expanded1 cells opened

start

(0,0)

goal

(4,4)

h = Manhattan distance to the goal

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L5	start=(0,0) goal=(4,4) h=h = Manhattan distance to the goal	A* orders cells by f = g + h: g is the cost so far, h guesses the cost still to go (h = Manhattan distance to the goal). A good guess steers the search towards the goal instead of in every direction.
2	L15	cell=(0,0) g=0 f=8	Expand (0,0) with g = 0, f = 8. New or improved open cells: (1,0) f=8, (0,1) f=8.
3	L15	cell=(1,0) g=1 f=8	Expand (1,0) with g = 1, f = 8. New or improved open cells: (2,0) f=8.
4	L15	cell=(2,0) g=2 f=8	Expand (2,0) with g = 2, f = 8. New or improved open cells: (3,0) f=8, (2,1) f=8.
5	L15	cell=(3,0) g=3 f=8	Expand (3,0) with g = 3, f = 8. New or improved open cells: (4,0) f=8, (3,1) f=8.
6	L15	cell=(4,0) g=4 f=8	Expand (4,0) with g = 4, f = 8. New or improved open cells: (4,1) f=8.
7	L15	cell=(4,1) g=5 f=8	Expand (4,1) with g = 5, f = 8. New or improved open cells: (4,2) f=8.
8	L15	cell=(4,2) g=6 f=8	Expand (4,2) with g = 6, f = 8. New or improved open cells: (3,2) f=10, (4,3) f=8.
9	L15	cell=(4,3) g=7 f=8	Expand (4,3) with g = 7, f = 8. New or improved open cells: (3,3) f=10, (4,4) f=8.
10	L10	return=8 expanded=9 opened=14	The goal is the smallest f in the open set: path length 8, found after expanding 9 cells (14 opened). The heuristic never overestimates, so no shorter path exists.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Shortest Path in Binary Matrix
Minimum Knight Moves
Sliding Puzzle

Advanced

Shortest Path in a Grid with Obstacles Elimination
Minimum Moves to Move a Box to Their Target Location

Key takeaways

A* pops the open vertex with the smallest f = g + h; with h = 0 it is Dijkstra.
An admissible heuristic never overestimates; then the first time the goal is popped the path is shortest.
A consistent heuristic satisfies h(u) <= w + h(v); it implies admissible and makes the closed set safe.
Use Manhattan for 4 directions and Chebyshev for 8 directions with unit-cost diagonals.