Which Algorithms Guarantee the Optimal Path?

The multi-select question that reappears in nearly every paper — one table to answer them all

The Question That Keeps Coming Back

Papers reuse this exact format:

"Given a state space with edge costs, which of the following can find the optimal path? (A) DFS (B) BFS (C) Dijkstra (D) Branch & Bound (E) A* (F) WA* for some w (G) SMGS"

One table answers every variant of this question.

The Master Table

Algorithm	Finds optimal path?	Condition	Why
DFS	✗	—	dives into whatever branch is first; ignores costs
BFS	only in unweighted graphs (fewest hops)	all edges equal	level-order = fewest edges, not cheapest cost
Dijkstra / UCS	✓	non-negative edge costs	expands nodes in true-cost order; black means final
Branch & Bound	✓	lower-bound estimates are valid; loop checking ok	always extends the cheapest partial path
A*	✓	$h$ admissible ( $h \leq h^*$ ), finite branching, edge costs $\geq \epsilon > 0$	Lemma-based proof (Week 5): Open always holds a node with $f \leq C^*$
WA* ( $w>1$ )	✗ (in general)	only if $h$ never overestimates even after weighting... practically no	inflates h → may chase a suboptimal goal before verifying cheaper ones
SMGS (Sparse/Simple Memory Graph Search)	✓	memory suffices for its bounded duplicate-detection	memory-bounded variant that keeps optimality where plain SMA*-style forgetting would lose it
Greedy Best-First	✗	—	follows $h$ blindly, ignores $g$ entirely

The Exam Answer Pattern

For weighted graphs with unknown heuristic properties: safe picks = Dijkstra, Branch & Bound. BFS only when the question says unweighted. A* only when admissibility is stated. WA* and greedy are traps. This exact combination appeared verbatim in multiple papers.

The Special Cases Exams Love

$w = 0$ in Weighted A*

$f(n) = g(n) + w \cdot h(n)\Big|_{w=0} = g(n) \implies \text{behaves like Dijkstra}$

So w = 0 ⇒ optimal (given non-negative costs). And as $w \to \infty$ , WA* approaches Greedy Best-First — fast but suboptimal. Memorize both endpoints.

$h = 0$ in A*

Same collapse: $f = g$ ⇒ Dijkstra/Branch-&-Bound behavior, still optimal but explores blindly.

BFS on unweighted graphs

BFS is optimal when cost = number of edges. The trap: papers say "edge costs may or may not be equal" — then BFS loses its guarantee.

DFID

Optimal in unweighted spaces if it doesn't prune via Closed (the new/open-nodes variant); the closed-node-pruning variant can miss shortest paths. See the DFID page.

Decision Flowchart

A*'s Fine Print (when the question adds conditions)

A* is guaranteed optimal iff ALL three hold (Week 5 lecture):

Finite branching factor
Edge costs bounded below by some $\epsilon > 0$ — merely positive isn't enough! Costs like $1, \frac{1}{2}, \frac{1}{4}, \ldots$ sum finite while giving infinitely many steps, trapping the search.
$h(n) \leq h^*(n)$ everywhere (never overestimates)

If a paper's option list includes A* but the stem says "heuristic properties not known" — you cannot select A*. That phrase exists precisely to eliminate it.

One-Line Summaries to Memorize

If asked about…	Answer with…
"cheapest-first, no heuristic"	Dijkstra — optimal, non-negative costs
"extend cheapest partial path"	Branch & Bound — optimal
" $f = g + Wh$ , large W"	fast, bounded-suboptimal, NOT optimal
"memory-bounded but still complete/optimal given room"	SMA*/SMGS family
"shortest in hops, infinite tree"	DFID without closed pruning
"follows h only"	greedy — never optimal in general

QuizA weighted graph, heuristic properties unknown. Which selections are SAFE for finding an optimal path?

QuizSetting w = 0 in Weighted A* makes the algorithm...

QuizWhy does the A* optimality proof require edge costs ≥ ε > 0 rather than just > 0?