A warehouse robot leaves the inbound dock for a pick bin. The floor is a 4-connected grid. Every step costs 1. The first router ran Dijkstra from the dock. It expanded the empty aisle that runs west — those cells were close to the source — while the bin sat two steps east. Nobody “forgot to prune.” They ordered the heap by distance so far, with no estimate of distance left. Manhattan to the bin would have said the west aisle is the wrong way. That estimate is A*.
A* is Dijkstra plus a heuristic: order the frontier by f = g + h, and the first settle is final when h never overestimates remaining cost. The layout is a weighted adjacency list (Graphs). The frontier is still a min-heap (Heaps). Settle, relax, and lazy re-push already live on the Dijkstra post — this one only changes the key. Families and the catalog live on the Algorithms Roadmap. It is not a game-engine tutorial, not a maps SDK, and not a reason to invent h = 1 because the assignment said “use A*.“
g is spent, h is remaining, f is the key
Dijkstra orders the heap by g: cost from the source so far. A* keeps that g, adds h(u) = an estimate of the cost still needed to reach the goal, and pops the smallest f(u) = g(u) + h(u). The procedure is point-to-point. You stop when the goal settles, not when every vertex has a distance.
h = 0 is Dijkstra. Every f collapses to g. The extra work in this post is choosing an h that is allowed to guess, and knowing what “allowed” means.
“I guessed 1” is not a heuristic. A constant you made up does not use the remaining work, does not pull toward the goal, and is Dijkstra with a shifted key — or inadmissible if you forget h(goal) = 0.
Admissible means never too high
h is admissible when it never overestimates true remaining cost: h(u) ≤ cheapest u ⇝ goal. First settle of the goal is then the shortest path. Underestimate is legal. Overestimate is not: the heap can pop a wrong goal path before a cheaper unfinished one.
On a 4-connected unit grid, two honest h functions:
- Manhattan
|Δrow| + |Δcol|— exact remaining if you never leave the grid and never hit a wall that forces a detour. Still a lower bound when walls exist, so still admissible. - Euclidean
sqrt(Δrow² + Δcol²)— straight-line lower bound. Also admissible while each step costs at least that Euclidean length.
Both are consistent (monotone) on that grid: h(u) ≤ w(u, v) + h(v) for every edge. Consistency is why the main sketch never reopens a settled vertex, same first-pop-is-final rule as Dijkstra. An inconsistent admissible h can improve g after a settle; you would reopen. This post names that once and keeps the sketch on consistent h — Manhattan on a 4-connected grid is the example.
Note: Directed or undirected is still the layout’s job. h is a function of a vertex and the goal, not of the edge you just walked. Non-negative weights stay required; a negative edge breaks first-pop-is-final the same way it breaks Dijkstra.
Order the heap by f, stop at the goal
Start at source s with a goal t. g[s] = 0, g elsewhere infinity. Push (f[s], s) where f[s] = h(s). Repeatedly:
- Pop the pair with the smallest
f. - Skip it if
gon the pair is stale — the lazy-repush rule from Dijkstra, not a decrease-key. - Settle the vertex. If it is
t, stop: thatg[t]is optimal whenhis admissible. - Relax each outgoing edge. If
g[u] + wimprovesg[v], write it and push(g[v] + h(v), v).
You do not scan every path. A good h just refuses to expand cells that cannot beat the best f already on the frontier.
Note: Unreachable t drains the heap the same as Dijkstra. Empty graph: g[s] = 0, one pop, done if s is t, else no path.
A walked pass that skips the wrong aisle
Four cells on a line, 4-connected, every step cost 1. Dock S, bin G two steps east, empty aisle W one step west. Dijkstra’s heap key is g; W and A both cost 1 from S, so Dijkstra settles W before G. Manhattan pulls east.
unit grid, 4-connected:
W --1-- S --1-- A --1-- G
h = Manhattan to G (cells on a line):
h(G)=0 h(A)=1 h(S)=2 h(W)=3
g: S=0, W=A=G=∞
pq by f = g + h: (f=2, g=0, S)
pop S settle S
S→W g[W]=1 h=3 f=4 push (4, W)
S→A g[A]=1 h=1 f=2 push (2, A)
pq: (2,A), (4,W)
pop (2,A) settle A
A→G g[G]=2 h=0 f=2 push (2, G)
pq: (2,G), (4,W)
pop (2,G) settle G stop
never pop W
path S→G: S → A → G cost 2Dijkstra (h = 0) after S holds (1, W) and (1, A). It settles W — a cell that cannot help — before the bin. A* never pops W because f = 4 loses to f = 2 on the east side. Same graph, fewer settles, because h is remaining work, not a guess.
Empty aisle past W would only make Dijkstra worse. A* still ignores it.
Java sketch
Weighted list as in the graph post: Edge(to, weight). Heap key is f. Stale pops compare g, the same skip as Dijkstra. h is a ToIntFunction you pass in — Manhattan, Euclidean, or v -> 0 if you want Dijkstra back.
record Edge(String to, int weight) {}
record Node(String v, int f, int g) {}
static int aStar(
Map<String, List<Edge>> g,
String src, String goal,
ToIntFunction<String> h) {
Map<String, Integer> gScore = new HashMap<>();
gScore.put(src, 0);
PriorityQueue<Node> pq = new PriorityQueue<>(
Comparator.comparingInt(Node::f)
.thenComparingInt(Node::g));
pq.add(new Node(src, h.applyAsInt(src), 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (cur.g() != gScore.getOrDefault(cur.v(), Integer.MAX_VALUE)) {
continue; // stale pair; Dijkstra post
}
if (cur.v().equals(goal)) {
return cur.g();
}
for (Edge e : g.getOrDefault(cur.v(), List.of())) {
if (e.weight() < 0) {
throw new IllegalArgumentException("negative weight");
}
long ng = (long) cur.g() + e.weight();
int best = gScore.getOrDefault(e.to(), Integer.MAX_VALUE);
if (ng < best) {
gScore.put(e.to(), (int) ng);
int f = (int) ng + h.applyAsInt(e.to());
pq.add(new Node(e.to(), f, (int) ng));
}
}
}
return Integer.MAX_VALUE; // unreachable
}Manhattan for a grid you have already keyed by cell name:
ToIntFunction<String> manhattan = v -> {
int[] p = coord.get(v); // {row, col}
return Math.abs(p[0] - goalR) + Math.abs(p[1] - goalC);
};Keep a prev map beside gScore if you must emit the path: when you write a better g[v], set prev[v] = u, then walk backward from the goal. Do not store every path prefix on the heap.
Note: Integer.MAX_VALUE + weight wraps. The long add is the guard, same as Dijkstra. Unreachable left at MAX_VALUE is a sentinel, not a cost you may add to. Do not reopen a settled vertex in this sketch — that is the inconsistent-h variant, not the Manhattan grid.
Complexity
Let V be vertices, E edges. Binary heap, lazy re-push. Each improved g pushes a pair. A useful h does not change the worst-case bound; it changes how many vertices you settle before the goal.
| Time | O(E log E) heap ops, usually written O(E log V) — same family as Dijkstra |
| Extra RAM | gScore, optional prev, heap of up to O(E) pairs |
| First pop of the goal | Shortest s ⇝ t when h is admissible |
First pop of every v | Shortest s ⇝ v when h is consistent |
h = 0 | Dijkstra; no pruning |
Glossary and the Big-O reading live on the hub. The bill that kills the warehouse robot is an h that overestimates, or a heap of g when remaining cost was obvious, not a missing Fibonacci heap.
If h is perfect (equals true remaining), A* settles vertices on one shortest path. Worst case you still look like Dijkstra.
When not to run A*
Skip it when:
- Every edge is 1 and you have no remaining-cost estimate. BFS already returns shortest path. A heap of
g + 0is Dijkstra; a heap of hop-count is cargo-cult of the name. - You cannot estimate remaining cost honestly. Use Dijkstra.
h = 0is the legal fallback, not a fake Manhattan on a graph with no geometry. hoverestimates. First settle of the goal can be the wrong path. Admissible or do not call it A*.- A weight is negative. First-pop-is-final is false. Same cousin as Dijkstra; this post does not walk it.
- A library already routes. Map SDKs, WMS routers, and graph DBs already run a shortest-path procedure. Pasting this sketch into a request path is the wrong system boundary.
Do not treat a guessed constant as a heuristic when the grid already has Manhattan. Do not reopen settled vertices because a later paragraph mentioned inconsistent h.
Also skip it when there is no single goal: all-pairs is a different procedure (Floyd-Warshall). This post is point-to-point.
JDK: a PriorityQueue of f, not an AStar class
There is no java.util.AStar. The library pieces are the frontier and the heuristic you supply:
- Heap:
PriorityQueuewithComparator.comparingInt(Node::f) gScore:Map<K, Integer>, stale skip as in the Dijkstra posth:ToIntFunction<K>— Manhattan, Euclidean, orv -> 0- Layout:
Map<K, List<Edge>>as in the graph post - Optional path: a
prevmap you fill whengimproves
Prefer A* when remaining cost has a geometry you can underestimate. Reach for Dijkstra when it does not. Reach for BFS when every edge is 1 and you are counting hops.
Do not remove from the heap to fake decrease-key. Do not implement a Fibonacci heap. Do not hard-code h = 1.
Cheat sheet
Job: point-to-point shortest path; weights ≥ 0; h admissible
Frontier: min-heap of (f, g, vertex) — PriorityQueue, f = g + h
Settle: first honest pop of the goal is final (admissible h)
every vertex, if h is consistent (Manhattan on 4-connected)
Relax: if g[u]+w < g[v], write g[v], push (g[v]+h(v), v)
Stale: pop with g != current gScore[v] → skip (Dijkstra post)
h = 0: Dijkstra
BFS: enough when every edge is 1 and you have no useful h
Inconsistent h: may reopen — not this sketch
JDK: PriorityQueue of f; ToIntFunction h; no AStar type
Do not: guess a constant; overestimate; maps-SDK paste; Fibonacci heapDo:
- Order the frontier by
f = g + h, not bygalone, when remaining cost is estimable. - Keep
hadmissible. Manhattan / Euclidean on a unit grid are the usual pair. - Re-push; skip stale pops. Link Dijkstra; do not reinvent decrease-key.
Don’t:
- Call a guessed constant a heuristic when the grid already has Manhattan.
- Overestimate remaining cost and still claim first-pop-is-final.
- Reopen a settled vertex on a consistent
h, or run this procedure past a negative edge. - Reach for a Fibonacci heap because a complexity table named one.
Wrap-up
A* is Dijkstra with the heap keyed by f = g + h instead of g. Pop the smallest f, skip stale pairs, stop when the goal settles. That settle is the shortest path when h never overestimates remaining cost. h = 0 is Dijkstra. Manhattan on a 4-connected grid is admissible and consistent; “I guessed 1” is neither a heuristic nor a reason to skip BFS on a unit graph with no geometry. The JDK gives you PriorityQueue and a ToIntFunction, not a turnkey router. Use BFS when hop count is the cost. Use Dijkstra when you cannot estimate remaining. Hand-roll the sketch when the estimate is honest and the goal is a vertex.
The next procedure in this wave leaves shortest paths: grow an MST by cheapest edge that does not cycle.