Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class BoundedPrunedYenKShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BoundedPrunedYenKShortestPath<V,E>
Type Parameters:
V - graph vertex type
E - graph edge type
All Implemented Interfaces:
KShortestPathAlgorithm<V,E>
public class BoundedPrunedYenKShortestPath<V,E> extends Object implements KShortestPathAlgorithm<V,E>
Experimental bounded-pruned variant of Yen's $k$ shortest loopless paths algorithm.

This class returns the same ordered sequence of path weights as YenKShortestPath (and is regression-tested against it) but tries to perform fewer spur shortest-path computations and fewer candidate materializations by deferring spur work behind lower-bound certificates.

Key idea

Standard Yen, when accepting a path $P$, eagerly enumerates every spur index of $P$, runs a shortest-path query under the appropriate banning, materializes the full candidate path, and pushes it into the candidate heap. For large $k$ on dense graphs this generates many candidates that will never be output.

The bounded-pruned variant defers each spur enumeration as a SpurTask carrying:

  • the parent accepted path,
  • the spur index in that parent,
  • the banned vertex set (the parent's prefix),
  • the root cost so far,
  • and a lower bound on any candidate it could ever produce: lowerBound = rootCost + reverseDistanceToSink[spurNode].

Reverse distances are computed once on the original graph. Because removing vertices/edges can only increase shortest-path distance, those reverse distances remain valid lower bounds even under arbitrary bans. So:

If the cheapest materialized candidate already satisfies candidate.cost ≤ task.lowerBound for every still-deferred task, it is safe to output the candidate as the next path — no deferred task could possibly produce something better.

Algorithm sketch

   firstPath = shortestPath(source, sink)
   accepted.add(firstPath)
   addSpurTasks(firstPath)
   while accepted.size < k:
       while taskHeap not empty AND
             (candidateHeap empty OR taskHeap.minLB < candidateHeap.minCost):
           materialize(taskHeap.pop())  // run the actual spur query, push candidate
       if candidateHeap empty: break
       next = candidateHeap.pop()
       accepted.add(next)
       addSpurTasks(next)

Exactness

The returned path-weight sequence equals that of YenKShortestPath. Tie-breaking among paths of equal weight is deterministic: a stable ordinal is attached to every candidate / task push so that two equal weights are broken by insertion order, which mirrors how the standard implementation eagerly inserts candidates as it accepts each path. The benchmark harness verifies the path-weight sequences match exactly across many graph families.

What this class does NOT yet claim

  • 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 optimisation only.

References

  • Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. Management Science, 17(11), 712–716. The original loopless k-shortest-paths algorithm whose spur step is reused here.
  • Martins, E. Q. V., & Pascoal, M. M. B. (2003). A new implementation of Yen's ranking loopless paths algorithm. 4OR — Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2), 121–133. Practical implementation notes that informed JGraphT's existing YenKShortestPath.
  • Aljazzar, H., & Leue, S. (2011). K*: A heuristic search algorithm for finding the k shortest paths. Artificial Intelligence, 175(18), 2129–2154. The closest prior published precedent for using admissible lower bounds (an A*-style heuristic on the reverse graph) to defer expansion of provably non-improving k-paths candidates. This class applies the same lower-bound-then-defer idea at the Yen spur-task level rather than at K*'s edge-expansion level.

  • Constructor Details

    • BoundedPrunedYenKShortestPath

      public BoundedPrunedYenKShortestPath(Graph<V,E> graph)
      Default constructor using DijkstraSpurEngine as the spur shortest-path back-end. This default mirrors the spur step of the existing YenKShortestPath for principle-of-least-surprise. Pass an AStarSpurEngine via BoundedPrunedYenKShortestPath(Graph, SpurShortestPathEngine) to opt into the reverse-distance A* heuristic — recommended for dense graphs or large k. The A* engine is exact (the heuristic is admissible by construction).
      Parameters:
      graph - the input graph (must not be null)

    • BoundedPrunedYenKShortestPath

      public BoundedPrunedYenKShortestPath(Graph<V,E> graph, SpurShortestPathEngine<V,E> engine)
      Constructor with a pluggable SpurShortestPathEngine.
      Parameters:
      graph - the input graph (must not be null)
      engine - the spur shortest-path engine to use (must not be null)

  • Method Details

    • getPaths

      public List<GraphPath<V,E>> getPaths(V source, V sink, int k)
      Description copied from interface: KShortestPathAlgorithm
      Get a list of k-shortest paths from a source vertex to a sink vertex. If no such paths exist this method returns an empty list.
      Specified by:
      getPaths in interface KShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      sink - the target vertex
      k - the number of shortest paths to return
      Returns:
      a list of the k-shortest paths

    • getStats

      public BoundedPrunedYenKShortestPath.Stats getStats()

    • engineName

      public String engineName()