Bounded-Pruned Yen + A* — interactive visualization

What you're watching — K-shortest paths with Yen

Both panels enumerate the K cheapest simple paths from source (blue) to target (purple), in order of cost.

Yen's algorithm (the shared backbone)

1. Find the first shortest path with a single Dijkstra (the initial path) — that's accept #1.
2. To produce the next path, walk every prefix of the previous accepted path. For each prefix:
   • The last node of the prefix is the spur node.
   • Ban every edge that, taken next, would re-create an already-accepted path sharing this same prefix (Yen rule).
   • Ban every node strictly inside the prefix so the spur can't loop back through it (simple-path rule).
   • Run a shortest-path search from the spur node to the target on this masked graph. prefix + spur path is a candidate.
3. The cheapest candidate is promoted to the next accepted path. Repeat until you have K.

Pick any two variants to compare

The A and B selectors in the controls bar choose the algorithm rendered in each pane. Five variants are wired up, matching the JGraphT JMH grid:

• Yen + Dijkstra — classical YenKShortestPath: a fresh Dijkstra at every spur, no deferral, no impossible-spur skip.
• Yen + A* (no bounded prune) — BoundedPrunedYenKShortestPath with setBoundedPruning(false). Same task structure as classical Yen but the spur engine is A* using the reverse-Dijkstra heuristic. Most of the headline speedup on the Andorra bench comes from this engine alone.
• BPYen + Dijkstra — bounded-prune lower-bound queue and impossible-spur skip, but the spur engine itself is plain Dijkstra (no heuristic). Useful for isolating the contribution of the bounded layer from the contribution of the A* engine.
• BPYen + A* (full) — everything on: A* spur engine, lower-bound deferral, impossible-spur skip.
• Eppstein — different family. Builds the shortest-path tree from the target, labels every non-tree edge with its sidetrack cost δ(u, v) = w(u, v) + dB(v) − dB(u), then enumerates the k lowest-cost walks from source to target. Walks may repeat vertices, so on graphs with cycles the answers differ from the Yen-family (which returns simple paths).

What to compare

Default selection — Yen + Dijkstra (left) vs BPYen + A* (right) — mirrors the original visualization: the right pane is dramatically faster on the chain example (zero spur searches after the initial path) and visibly tighter on the grid (A* heads straight at the target). Set both panes to A* engines (one with the bounded-prune layer, one without) to see how small the bounded layer's marginal win is once A* is in play; set one pane to Eppstein to compare a fundamentally different algorithm.

What you're watching — AllDirectedPaths forward pruning

AllDirectedPaths enumerates every directed s → t walk of length at most maxPathLength. Before enumeration starts, it pre-decorates each edge with the minimum number of edges to a target through that edge — anything not on a short-enough route to a target is dropped from the search space.

Shared scaffolding (both panels)

A reverse BFS from the target set (here, just T) walks backwards along incoming edges. For each edge u → v encountered while popping v, we record dB(edge) = 1 + dB(v), the minimum backward distance from u to the target through this edge.

Left — backward BFS only (baseline)

Mark every edge whose head is backward-reachable to a target within budget hops. Nothing checks whether the edge's tail is itself reachable from a source, or whether a feasible source → target walk through this edge could even fit within the budget. That includes "orphan" branches that reach the target but have no incoming connection from the source — wasted bookkeeping.

Right — forward pruning (new)

Run a one-time forward BFS from the sources first; cache dF(v) for every vertex it reaches (highlighted with a cyan dashed halo). Then, during the backward BFS, gate each candidate edge u → v by two conditions:

• Forward-reachability. If u isn't in the forward-BFS map at all, no source can reach this edge — drop it.
• Length gate. If dF(u) + 1 + dB(v) > budget, no walk through this edge can stay within the length limit — drop it.

Edges retained satisfy both conditions, so each one lies on at least one feasible source → target walk of length ≤ budget. Every simple path is also a walk, so the prune preserves the exact answer in both simple-only and all-walks modes.

What to watch

• On the Garden example, the orphan branch x → y → T is happily marked by the left pane but dropped on the right (those edges turn red, never green) — their source side is unreachable from S.
• On the Tight-budget diamond with maxPathLength = 2, the right pane drops the long route S → b → c → T entirely. The left pane retains parts of it because individual edges fit under the backward budget, even though no length-2 walk can use them.
• The edges retained counter is the size of the decoration map the path- enumeration step will iterate over — a smaller map is straight-line faster.

What you're watching — single shortest path

Both panels answer the same question: what is the cheapest path from source (blue) to target (purple), and how many nodes did the algorithm have to look at to find it?

Shared mechanics

Both maintain a priority queue (the open set) of nodes whose tentative cost from the source is known. On each step the algorithm pops the cheapest entry — we say it expands that node — and relaxes each outgoing edge: for every neighbour, if the new tentative cost through the just-expanded node beats the current best, the neighbour is updated and (re)pushed into the queue. The green tint marks nodes that have been expanded; that set is the algorithm's effort.

Left panel — standard Dijkstra

Priority key is g(v), the cost from source to v. Dijkstra always expands the cheapest unsettled node in the whole graph, regardless of where the target sits. That's why its frontier grows as a roughly circular wave outward from the source. On the grid, Dijkstra ends up settling almost every node before it touches the target.

Right panel — A* with reverse-Dijkstra heuristic

Priority key is f(v) = g(v) + h(v), where h(v) is an estimate of the remaining cost from v to the target. Because h must be admissible (never overestimate), the heuristic used here is computed by a one-time reverse Dijkstra from the target on the original graph — that's exact on the unconstrained graph. With an exact heuristic, A* expands only nodes on a shortest path and walks straight from source to target.

Trade-off

A*'s win isn't free: that reverse Dijkstra is itself a full Dijkstra from the target. If you only ever need a single shortest path, plain Dijkstra is usually the better choice. The heuristic earns its keep when it's reused across many searches — exactly what happens inside BoundedPrunedYenKShortestPath, where it heuristic-guides every spur and acts as the lower-bound oracle for pruning.

What to watch

• Nodes expanded — the algorithm's primary effort. On the grid this is where A* wins big.
• Edges relaxed — every time a neighbour's tentative distance was tightened. With an exact heuristic A* relaxes the same edges as Dijkstra along the path but skips most of the off-path relaxations.
• Path cost and path length — the answer. Both algorithms agree.
• The chain example has only one possible path, so Dijkstra and A* take the same number of expansions. The grid is where A*'s win is dramatic.