Class BaseShortestPathAlgorithm<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
Direct Known Subclasses:
AStarShortestPath, BaseBidirectionalShortestPathAlgorithm, BellmanFordShortestPath, BFSShortestPath, ContractionHierarchyBidirectionalDijkstra, DeltaSteppingShortestPath, DijkstraShortestPath, FloydWarshallShortestPaths, IntVertexDijkstraShortestPath, JohnsonShortestPaths, TransitNodeRoutingShortestPath
abstract class BaseShortestPathAlgorithm<V,E> extends Object implements ShortestPathAlgorithm<V,E>
A base implementation of the shortest path interface.

  • Field Details

    • GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

      protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
      Error message for reporting the existence of a negative-weight cycle.
      See Also:

    • GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

      protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
      Error message for reporting that a source vertex is missing.
      See Also:

    • GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

      protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
      Error message for reporting that a sink vertex is missing.
      See Also:

    • graph

      protected final Graph<V,E> graph
      The underlying graph.

  • Constructor Details

    • BaseShortestPathAlgorithm

      public BaseShortestPathAlgorithm(Graph<V,E> graph)
      Constructs a new instance of the algorithm for a given graph.
      Parameters:
      graph - the graph

  • Method Details

    • getPaths

      public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
      Compute all shortest paths starting from a single source vertex.
      Specified by:
      getPaths in interface ShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths

    • getPathWeight

      public double getPathWeight(V source, V sink)
      Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
      Specified by:
      getPathWeight in interface ShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      sink - the sink vertex
      Returns:
      the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists

    • createEmptyPath

      protected final GraphPath<V,E> createEmptyPath(V source, V sink)
      Create an empty path. Returns null if the source vertex is different than the target vertex.
      Parameters:
      source - the source vertex
      sink - the sink vertex
      Returns:
      an empty path or null null if the source vertex is different than the target vertex