Subject: [Proposal] Exact bounded-pruned Yen variant with pluggable spur shortest-path engines
Shai Eilat
Hi all,
Following the contributor guide ("discuss first, then PR"), I'd like feedback on a proposed contribution before opening a pull request.
The proposal adds a new exact Yen-family implementation, BoundedPrunedYenKShortestPath, alongside the existing YenKShortestPath, with two separable optimisations: a pluggable spur shortest-path engine abstraction (including an AStarSpurEngine) and a bounded-pruned Yen driver. They are separable: the A* engine improves individual spur queries, while the bounded-pruned layer reduces how many spur queries and candidates need to be materialised. Each is independently useful and can be reasoned about in isolation.
Primary: A* spur engine with reverse-distance heuristic. The larger lever on dense graphs. A new SpurShortestPathEngine abstraction lets the spur shortest-path back-end be swapped, and an AStarSpurEngine ships that uses an admissible heuristic (single reverse-Dijkstra precomputed once per getPaths call) to terminate spur queries after far fewer vertex expansions than a plain Dijkstra. This alone accounts for most of the speedup observed on dense inputs in the benchmark below — and crucially, it is exact by construction.
Secondary: bounded-pruned Yen layer. A smaller, incremental optimisation on top. Standard Yen eagerly materialises every spur. The bounded-pruned layer defers each spur as a SpurTask keyed by an admissible lower bound, and only materialises tasks that could still beat the cheapest already-known candidate. Output-sensitive; degrades gracefully to standard-Yen behaviour when the certificate cannot prune.
Both improvements return the same ordered sequence of path weights as YenKShortestPath and are regression-tested against it. The contribution does not modify YenKShortestPath or YenShortestPathIterator.
MotivationStandard Yen runs a single-target Dijkstra for every spur enumeration. On dense graphs each Dijkstra expands a large fraction of the vertex set even though most of that work is irrelevant to the source-to-sink question being asked.
Once we are willing to compute reverse distances from the sink (one Dijkstra on the edge-reversed graph, paid once per getPaths call), we have an admissible heuristic available after that one reverse shortest-path computation for every subsequent spur query: reverse-distance removal-monotonicity is a standard property of Dijkstra on non-negative weights (removing vertices/edges only increases shortest-path distances on the masked graph). Plugging that heuristic into the existing AStarShortestPath (via a MaskSubgraph for bans) gives an exact spur shortest path with typically far fewer expansions. On the densest benchmark case (n=2000, m=30000) the spur queries finish after ~1 000 vertex expansions in total across the run, and the wall-clock cost of the spur step falls substantially in this benchmark.
A* returns an exact shortest path under an admissible heuristic and non-negative edge weights. The reverse distances are computed on the original graph, so they are admissible on every banned-subgraph query. There is no exactness trade-off to weigh against the speedup.
For large k on dense graphs, standard Yen also materialises many candidates that are never output. The optimisation is well-known in the routing / k-paths literature: defer spur computation behind a lower-bound certificate and only materialise tasks that can still beat the cheapest known candidate.
The lower-bound certificate uses the same reverse-distance precomputation: for a deferred SpurTask with lowerBound = rootCost + reverseDistanceToSink[spurNode], every path eventually produced by that task — irrespective of how many bans are later added — has cost ≥ lowerBound. This is admissible (Dijkstra monotonicity under bans) so candidates can be safely emitted while deferred tasks have a larger lower bound than the cheapest materialised candidate.
In adversarial graphs (every path has near-identical lower bound) the certificate cannot prune anything and the algorithm degrades gracefully to standard-Yen behaviour.
The two improvements live in separate layers and can be reasoned about independently.
Improvement 1 — SpurShortestPathEngine + AStarSpurEngine. A new package interface, SpurShortestPathEngine<V,E>, abstracts the spur SP query: input is (graph, source, sink, bannedVertices, bannedEdges, reverseDistancesToSink), output is the shortest path under the bans (or null). Two engines ship, both delegating to existing JGraphT shortest-path algorithms rather than duplicating them:
DijkstraSpurEngine — wraps the input graph in a MaskSubgraph with the banned vertices/edges and delegates to DijkstraShortestPath. Behaviour equivalent to the spur step of today's YenKShortestPath.
AStarSpurEngine — same MaskSubgraph ban handling, builds an AStarAdmissibleHeuristic from reverseDistancesToSink, and delegates to the existing AStarShortestPath (Joris Kinable et al., 2015). The heuristic is admissible by construction, so A* terminates on the exact shortest spur path.
Both engines are thin adapters (≈100 LOC each, including Javadoc) that reuse the well-tested JGraphT implementations rather than reinventing them. The engine API itself is intentionally narrow (one method, plus a name for stats output) so future engines (e.g. bidirectional Dijkstra, contraction hierarchies for road-network use cases) can be added without touching Yen.
Improvement 2 — BoundedPrunedYenKShortestPath. The Yen-level driver. Defers each spur index of an accepted path as a SpurTask carrying the parent path, the spur index, the prefix bans, the root cost, and the lowerBound. Tasks are kept in a min-heap keyed by lowerBound. A task is only materialised when its lower bound could still beat the cheapest already-materialised candidate. The materialisation step itself uses the configured SpurShortestPathEngine — so improvement 2 cleanly composes on top of improvement 1.
An exact impossible-spur skip is folded into improvement 2 (always on). Before enqueuing a SpurTask, compute the Yen banned edges for that spur and check whether the spur node has any surviving outgoing edge under both prefix-vertex bans and Yen banned-edge bans. If not, skip the task. Adding more bans later can only remove legal exits, never add them, so a "no legal exit" verdict here is stable for the rest of the run — the skip is exact, not heuristic. This catches the path-chain pathology cleanly: every spur on a single-path chain has its only outgoing edge banned by the Yen rule, so all n−1 spurs are skipped and zero spur shortest-path queries are issued.
The no-engine constructor delegates to DijkstraSpurEngine for conservative default behaviour (mirrors the spur step of today's YenKShortestPath); AStarSpurEngine is available through the two-argument constructor and is the recommended option for dense graphs or larger k.
Improvement 1 (A engine):*
Not a free lunch on sparse graphs. The reverse-distance precomputation is a one-time O(m + n log n) cost per getPaths call. On graphs where each spur Dijkstra is already small (e.g. 4-connected grids), the precomputation can outweigh the per-spur savings.
Not a complexity improvement. A* is O(m + n log n) per call in the worst case, the same as Dijkstra.
Improvement 2 (bounded-pruned Yen layer):
No proven better worst-case complexity. Yen's O(k·n·(m + n log n)) remains the upper bound. The bounded-pruned layer is an output-sensitive constant-factor optimisation — not new asymptotics.
Not a replacement for YenKShortestPath. On sparse graphs where each spur SP query is already cheap, the extra heap/certificate machinery costs more than it saves (see road_grid_30x30 row below). It is a complementary alternative that users can opt into when the graph is dense or k is large.
jgrapht-core/src/main/java/org/jgrapht/alg/shortestpath/
BoundedPrunedYenKShortestPath.java (main algorithm)
SpurShortestPathEngine.java (engine interface)
DijkstraSpurEngine.java (single-target Dijkstra)
AStarSpurEngine.java (A* with reverse-distance heuristic)
jgrapht-core/src/test/java/org/jgrapht/alg/shortestpath/
BoundedPrunedYenKShortestPathTest.java (24 tests, all PASS)
jgrapht-demo/src/main/java/org/jgrapht/demo/
BoundedPrunedYenBenchmark.java (standalone benchmark, deterministic seeds)
BoundedPrunedYenKShortestPathTest — 24/24 PASS, JUnit 5. Coverage:
Hand-built cases:
negative-k throws, k=0 returns empty, unreachable sink returns empty
diamond with heavy direct edge, tied-equal-weight paths
cyclic graph (loopless paths only)
layered DAG (k ∈ {1, 2, 5, 10}), random DAG (n=80, m=320, k=20), 8×8 grid
Edge cases:
k larger than total paths (graceful termination)
zero-weight edges
single-edge graph
source == sink (returns the trivial zero-length walk to match YenKShortestPath)
large k on a dense small DAG (stress dedup + heap-empty termination)
negative-weight edge: throws IllegalArgumentException
Both engines explicitly cross-checked against YenKShortestPath on five seeded layered DAGs.
Property-style fuzz suites:
40 random DAGs (n ∈ [8, 87], extras random, k ∈ [1, 25], independent seeds)
30 random cyclic digraphs (n ∈ [6, 45], m ≈ n + extras, k ∈ [1, 20])
5 seeds × 9 grid shapes (3×3 / 5×5 / 8×8) = 45 grid cases
Impossible-spur skip:
Skip eliminates every spur task on a 100-node path chain (spurTasksCreated == 0, skippedImpossibleSpurTasks == n−1)
Single-path chain returns only the one available path under both engines
Every regression test asserts the same ordered weight sequence as YenKShortestPath. Each fuzz failure prints its seed for reproducibility. The benchmark harness re-checks exactness before recording every measured row and aborts the case if the weight sequence diverges.
One real bug was found and fixed during this expanded testing. The engines previously returned null when source == sink, causing BoundedPrunedYenKShortestPath to return an empty list while YenKShortestPath returned the trivial zero-length walk. Both engines now return that walk explicitly. Caught by testSourceEqualsSink. Mentioned here because the test/fix lives in the same branch as the proposal — there is no behavioural difference exposed to existing API users since the new class is new.
Standalone benchmark in jgrapht-demo, median of 5 runs after 2 warm-up iterations, deterministic graph generators with fixed seeds. JDK 21, Windows 11, single run on a developer machine — numbers are illustrative, not production benchmarks. Input space (14 cases): layered DAGs of several shapes, random DAGs (uniform and heavy-tailed weights, n up to 5 000, m up to 60 000), Erdős–Rényi-style cyclic digraphs (n up to 1 500), 4-connected grids (30×30 and 50×50), an adversarial near-uniform-weight DAG designed to defeat the lower-bound certificate, and a degenerate single-path chain (path_chain_1000) included specifically to surface a worst-case overhead pattern for the bounded layer.
The benchmark reports two speedup columns: vsBaseline (vs YenKShortestPath = Yen+Dijkstra) and vsSameEng (vs an eager Yen running the same spur engine — isolates the bounded-pruning layer separately from the engine swap; the eager reference is implemented in the benchmark file only and is regression-checked against YenKShortestPath on every case).
Compact summary (full per-row table including timings, stats columns, and vsSameEng numbers is in the benchmark output / branch / PR):
Numbers below are speedups vs YenKShortestPath (Yen+Dijkstra) baseline. bounded+a* is BoundedPrunedYenKShortestPath with AStarSpurEngine.
Speedups are vs the YenKShortestPath baseline (Yen+Dijkstra). All variants verified to produce the identical ordered weight sequence as the baseline.
The compact table shows three speedup columns vs the Yen+Dijkstra baseline:
bounded+dijkstra — bounded-pruned Yen layer with the same Dijkstra spur back-end as the baseline. This is the bounded-pruning layer's contribution in isolation (no engine change).
yen+astar — eager Yen with the new A* spur engine (no bounded-pruning). This is the engine swap in isolation.
bounded+astar — both improvements composed.
Reading them:
Improvement 1 — A spur engine.* The yen+astar column is the engine swap on its own. It is consistently a win on dense inputs (2.9×–61× across the layered, random-DAG and ER cases) and within noise on the sparse 30×30 grid (0.97×). On the 50×50 grid it gives 2.45× because the larger sink distance gives the heuristic more to do. On a degenerate single-path chain it is essentially neutral (1.22×).
Improvement 2 — bounded-pruned Yen layer + impossible-spur skip. The bounded+astar column shows both improvements composed. Reading the same-engine ratios (bounded+astar / yen+astar):
Wins clearly: layered_small 1.65×, layered_medium 1.25×, dag_sparse_1000 1.81×, dag_uniform_500 1.45×, dag_dense_300_k200 2.27×, dag_heavy_2000 1.33×, path_chain_1000 1.30×.
Roughly neutral (within ±5%): layered_wide 0.99×, dag_heavy_5000 1.09×, er_digraph_500 0.98×, er_digraph_1500 1.04×, road_grid_30x30 1.05×, grid_50x50 0.98×, adversarial_500 0.97×.
No clear losses.
At the Dijkstra level (bounded+dijkstra column) the layer is worth 1.70×–9.96× on the layered/random-DAG cases. It is still a regression on the sparse / wide-cycle graphs at this engine level (er_digraph_500 0.51×, er_digraph_1500 0.49×, grid_50x50 0.29×) — the combination of bounded scheduling with the Dijkstra engine is not a good fit for those sparse / wide-cycle cases.
On path_chain_1000 specifically. Earlier drafts of this branch had a catastrophic 25× slowdown here — the bounded loop enumerated n−1 spur tasks for a graph that has no second path. The exact impossible-spur skip catches every one of those: zero spur shortest-path queries are issued. The Dijkstra-engine variant is still slower than the baseline (0.09×) because the residual O(n) per-spur ban computation costs ~9ms on n=1000, more than the baseline's single Dijkstra takes. The A*-engine variant flips to a small win (1.58×) since A*'s first-call work is also smaller. The single-path chain is the canonical pathological case for any bounded / candidate-deferral algorithm, and the exact skip resolves the catastrophic case fully at the A* engine level.
Honest caveats:
On the sparse 4-connected grid, both improvements are weak at the small size and only marginally helpful at the larger size. Documentation should warn about this.
The bounded layer is not a uniform win on top of A*. Across the 14 cases it wins clearly on 7 and is roughly neutral on 7. None of the 14 cases is a regression after the impossible-spur skip is applied.
Composing both improvements is multiplicative where each helps. The headline dag_heavy_2000 70.77× speedup is largely the A* engine doing the work (53.09× of it); the bounded layer adds 1.33× on top there. On dag_sparse_1000 the multiplication is more even (13.47× from A*, 1.81× from the layer = 24.44× combined).
API placement. Does it make sense to expose SpurShortestPathEngine as public API in org.jgrapht.alg.shortestpath, or should it live under an .spi / internal sub-package until at least one external engine implementation is in tree?
Default engine. The current draft uses DijkstraSpurEngine as the no-engine default — chosen for principle-of-least-surprise: it mirrors the spur step of today's YenKShortestPath, avoids the reverse-distance precomputation cost on workloads that wouldn't benefit (e.g. very sparse grids), and makes A* an explicit opt-in for callers who know their workload is dense or large-k.
I'm happy to flip the default to AStarSpurEngine if the project would prefer the better-on-average behaviour as the default given that the heuristic is admissible by construction (no exactness trade-off). Please tell me what the project prefers.
Future direction for YenKShortestPath itself. YenKShortestPath is unchanged in this proposal, but the two improvements have different futures:
Improvement 1 (A* spur engine) is a large win on the tested dense graph families and a small regression on the tested sparse grid case. Would the project consider a follow-up where YenKShortestPath itself gains an opt-in A* spur back-end, or is the side-by-side BoundedPrunedYenKShortestPath the preferred home for it long-term?
Improvement 2 (bounded-pruned layer) is more clearly opt-in — its value is workload-dependent and it would be surprising as the default behaviour of the existing class. I'd expect this to remain a sibling algorithm regardless.
Citation. The lower-bound certificate idea is folklore in the routing literature (it's how a number of practical k-paths systems work) but I do not have a single canonical paper to cite for this specific phrasing. Would the maintainers want a survey-style reference, or is the inline correctness argument sufficient given the regression suite?
Benchmark scope. Should the BoundedPrunedYenBenchmark ship in jgrapht-demo (current), or is there a preferred home for empirical benchmarks in the project?
All 24 unit tests pass (12 hand-built + 6 edge cases + 1 cross-engine smoke + 3 property-style fuzz suites covering ~115 random graph configurations + 2 impossible-spur skip tests).
Full jgrapht-core test suite is green: 6899/6899 PASS (15 skipped — unrelated upstream DoublyLinkedListTest parameterised tests that abort one parameter combination via Assumptions.abort()).
All 14 benchmark cases × 4 variants = 56 measurements are exact (identical ordered weight sequence to YenKShortestPath).
mvn install -DskipTests builds clean across all modules.
mvn checkstyle:check -P checkstyle and mvn javadoc:aggregate are clean.
Both engines delegate to existing JGraphT implementations (DijkstraShortestPath, AStarShortestPath) via MaskSubgraph for ban handling. The engines are thin adapters; no shortest-path logic is duplicated. (An earlier draft of this branch had hand-rolled A* and Dijkstra implementations inside the engines; that was refactored away before this proposal.)
The benchmark uses an eager-Yen-with-engine reference baseline (implemented in the benchmark file only, regression-checked against YenKShortestPath on every case) so the "vsSameEng" column reports an apples-to-apples comparison that does not conflate the bounded-pruning layer with the engine choice.
An earlier draft included a third "experimental BMSSP-style" engine; it was removed before this proposal because it was not exact on one benchmark case. Exactness is non-negotiable for a library algorithm and I did not want to ship anything with a correctness asterisk. A bounded-SSSP engine is plausible follow-up work and would only be proposed if/when it is exact and grounded in a publication.
Happy to:
post a branch URL for review,
run the benchmark on additional graph families the list suggests,
restructure the API per maintainer preference (point 1),
flip the default engine per maintainer preference (point 2).
mvn checkstyle:check -P checkstyle and mvn javadoc:aggregate already pass clean on the working branch, copyright headers follow the (C) Copyright YYYY-YYYY, by <author> and Contributors. form, and the formatter has been run. If the list is broadly comfortable with the design direction I'll open the PR; if any of the open questions need a different answer I'll fold the changes in first.
Thanks for reading.
— Shai Eilat
John Sichi
--
You received this message because you are subscribed to the Google Groups "jgrapht-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jgrapht-dev...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/jgrapht-dev/d3753a41-3d5c-4e7d-9b91-ae0584cb3d81n%40googlegroups.com.
Shai Eilat
Hi John,
Thank you for the quick response and helpful guidance.
I incorporated your feedback into the PR here:
https://github.com/jgrapht/jgrapht/pull/1338
In particular:
SpurShortestPathEngine is kept in org.jgrapht.alg.shortestpath.
The default constructor uses DijkstraSpurEngine for conservative behavior.
YenKShortestPath and YenShortestPathIterator are unchanged; the new implementation is opt-in.
The benchmark was moved under the existing perf benchmark location/pattern rather than jgrapht-demo.
I added JMH results as the primary benchmark evidence and kept the wider synthetic benchmark only as directional supporting data.
I added a reference for the related k-shortest paths literature.
Separately, I have three smaller fork-staging PRs lined up in my fork for self-review before deciding whether to send them upstream:
- https://github.com/seilat/jgrapht/pull/1 — optimize DijkstraManyToManyShortestPaths.getPaths(V) to run one source search
- https://github.com/seilat/jgrapht/pull/2 — avoid unused pathVertices rebuild in AllDirectedPaths non-simple mode
- https://github.com/seilat/jgrapht/pull/3 — prune source-unreachable branches in AllDirectedPaths preprocessing
I’m not asking for review on those yet; just mentioning them for visibility. I’ll wait for feedback on the Yen PR first and only bring these upstream one at a time if/when it makes sense.
Thanks again for the review direction. I’m happy to adjust the API, naming, benchmark structure, or documentation further based on maintainer preference.
I hope users will find this useful.