Before you can read the parent note (A* topic) you must own a small pile of symbols. This page builds each one from nothing, in an order where every new idea only leans on ones already defined.
Everything here lives on a graph. Before any formula, picture it.
In the figure the dots are nodes, the lines are edges, the number written on each line is its weight c(u,v), and the entire drawing together is the graph. A path is just a chain of edges you walk one after another; its total cost is the sum of the weights you stepped on. This is the raw stage on which A* plays.
Picture: a single arrow from dot u to dot v with a price tag hanging off it. That price tag isc(u,v). We need this symbol because every later quantity — g, h, the whole triangle inequality — is built by adding up these edge prices.
Two nodes are special. Everything A* does is measured relative to them, so they deserve their own symbols.
Picture two dots circled specially in the graph: one labelled s where you plant your flag to begin, one labelled t where the treasure sits. Every cost below is either "distance from s" or "distance to t".
In the figure, the red path from s to node n is the route we walked; g(n) is the sum of the numbers along that red path. Look how it is entirely behind us — g only ever measures road we have already travelled.
g looks backward toward s. To aim at t we need something that looks forward.
In the figure the dashed red arrow is the guessh(n) — a straight peek from n toward t. The wiggly black line is the true cheapest remaining road h∗(n) we'd actually have to walk. Notice the dashed guess is shorter or equal — that's the whole game, and it has a name (Section 6).
The figure stitches the two halves: solid red = g(n) (behind us, back to s), dashed red = h(n) (guess ahead, toward t). Their sum, the full red span from s to tthrough n, is f(n).
Now we can state the single condition that makes A* trustworthy.
Picture Section 4's figure again: the dashed guess sitting at or below the true wiggly path. That "at or below" is admissibility. It matters because if a guess ever overpromised ("goal is far!") on a genuinely-good node, A* might skip that good node and return a worse path — the failure shown in the parent's Worked Example 2.
Admissibility talks about each node alone. Consistency talks about neighbours.
Consistency is stronger than admissibility: the parent proves consistent ⟹ admissible (arrow one-way: C → A). Its payoff is that the score f never dips as you go deeper, which lets A* close a node once and never reopen it.
A* has to keep asking "which node has the smallest f?" thousands of times. That question needs the right container.
Picture a bucket that automatically floats the cheapest-f node to the top; you always scoop from the top. Without it, finding the min every step would be slow and A* would lose its speed advantage.
Read it bottom-up: the graph plus a start s and goal t give costs; costs build g; a chosen guess builds h; together they build f; the two honesty rules (admissible, consistent) keep f trustworthy; the min-heap makes "pick smallest f" fast — and that is A*.
