The graph structure from the last lesson is just connections. These algorithms decide the order you visit them in, and that order changes everything: whether you find the shortest path, how much work you waste exploring dead ends, and whether you even need to know where the goal is.
Section 2
BFS vs DFS: same graph, same start, different order
Breadth-first uses a queue: explore everything one step away before going further. Depth-first uses a stack: commit to one path as deep as it goes before backtracking. Same graph, same starting node, watch the order genuinely diverge.
Queue (BFS)
Algorithm
Controls
Visit order so far
Exam tips
BFS finds the shortest path in terms of number of edges on an unweighted graph, guaranteed, because it explores in strict distance order.
DFS uses far less memory in a wide graph (only needs to remember the current path), but gives no such shortest-path guarantee, and can go a long way down the wrong branch before backtracking.
Section 3
Dijkstra's shortest path
Edges now have weights (real costs, not just connections). Dijkstra's always expands the cheapest-so-far node next, regardless of which direction it's actually in.
Controls
Section 4
A*: the same problem, with a hint about direction
Same graph, same start and goal, same guaranteed-shortest answer. The only difference: A* also knows the straight-line distance from each node to the goal, and uses it to avoid wasting time on nodes that are cheap to reach but clearly going the wrong way.
Controls
Head to head
0
Dijkstra's nodes explored
0
A* nodes explored
Both will report the same shortest distance. Watch whether A* needs fewer steps to get there.
Exam tips
A* explores nodes in order of (distance so far) + (estimated distance remaining), Dijkstra's is really just A* with that second term always set to zero.
The dashed nodes below the main graph are a dead-end branch that happens to be very cheap to reach, exactly the kind of trap Dijkstra's has no way to avoid, since it has no notion of "which way is the goal".
A* is only as good as its heuristic. A heuristic that overestimates the true remaining distance can cause it to miss the actual shortest path, straight-line distance is safe here because it can never overestimate a real path length.
Section 5
Proof: an overestimating heuristic genuinely breaks A*
The exam tip above is easy to state and easy to forget why it matters. Here's a small, deliberately built example where it actually goes wrong, not a near-miss, a genuinely incorrect shortest distance.
Heuristic for node B
The true shortest route is S \u2192 B \u2192 G, total cost 100. Watch what happens to the answer as B's heuristic gets inflated further and further beyond the truth.
Exam tips
This property, never overestimating the true remaining distance, is called admissibility. It's the one condition that guarantees A* still finds the true shortest path.
Notice the algorithm doesn't crash or get confused, it terminates cleanly and confidently, just with the wrong answer. That's what makes a bad heuristic dangerous: nothing visibly goes wrong.