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

Class DijkstraSpurEngine<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.DijkstraSpurEngine<V,E>
Type Parameters:
V - graph vertex type
E - graph edge type
All Implemented Interfaces:
SpurShortestPathEngine<V,E>
public class DijkstraSpurEngine<V,E> extends Object implements SpurShortestPathEngine<V,E>
Spur shortest-path engine that delegates to JGraphT's DijkstraShortestPath. Bans are applied by wrapping the input graph in a MaskSubgraph so we do not duplicate or modify the underlying Dijkstra implementation. The reverseDistancesToSink hint is unused here; it is consumed by the bounded-pruned Yen driver itself, not by this engine.

Edge weights must be non-negative (a Dijkstra precondition).

The expandedVertices() counter is reported as 0 because DijkstraShortestPath does not expose a per-call expansion count. The metric is documented as best-effort on SpurShortestPathEngine.

  • Constructor Details

    • DijkstraSpurEngine

      public DijkstraSpurEngine()

  • Method Details

    • findPath

      public GraphPath<V,E> findPath(Graph<V,E> graph, V source, V sink, Set<V> bannedVertices, Set<E> bannedEdges, Map<V,Double> reverseDistancesToSink)
      Description copied from interface: SpurShortestPathEngine
      Compute an exact shortest path from source to sink on graph ignoring vertices in bannedVertices and edges in bannedEdges.
      Specified by:
      findPath in interface SpurShortestPathEngine<V,E>
      Parameters:
      graph - original graph (engines should not mutate it)
      source - source vertex of the spur query
      sink - target vertex of the spur query
      bannedVertices - vertices to ignore (must not include source or sink)
      bannedEdges - edges to ignore
      reverseDistancesToSink - optional hint, lower-bound distances from each vertex to sink computed on the original graph; may be null for engines that do not need it
      Returns:
      the shortest path or null if no path exists in the masked graph

    • expandedVertices

      public long expandedVertices()
      Description copied from interface: SpurShortestPathEngine
      Number of vertices the engine has expanded (popped from its open set) since the last SpurShortestPathEngine.resetCounters() call. Best-effort metric used by benchmarks; engines that do not track expansion (e.g. those delegating to a back-end without a public expansion counter) may return 0.
      Specified by:
      expandedVertices in interface SpurShortestPathEngine<V,E>
      Returns:
      number of vertices popped from the engine's open set since the last reset, or 0 when not tracked

    • pathQueries

      public long pathQueries()
      Description copied from interface: SpurShortestPathEngine
      Number of shortest-path queries answered since the last SpurShortestPathEngine.resetCounters() call.
      Specified by:
      pathQueries in interface SpurShortestPathEngine<V,E>
      Returns:
      number of shortest-path queries answered since the last reset

    • resetCounters

      public void resetCounters()
      Description copied from interface: SpurShortestPathEngine
      Reset internal counters. Called by BoundedPrunedYenKShortestPath between independent runs so that counters report per-run statistics.
      Specified by:
      resetCounters in interface SpurShortestPathEngine<V,E>

    • name

      public String name()
      Description copied from interface: SpurShortestPathEngine
      Symbolic name of the engine, used in benchmark reports.
      Specified by:
      name in interface SpurShortestPathEngine<V,E>
      Returns:
      a short human-readable identifier for this engine