Class JohnsonShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.JohnsonShortestPaths<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
public class JohnsonShortestPaths<V,E> extends BaseShortestPathAlgorithm<V,E>
Johnson's all pairs shortest paths algorithm.

Finds the shortest paths between all pairs of vertices in a sparse graph. Edge weights can be negative, but no negative-weight cycles may exist. It first executes the Bellman-Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph.

Running time is $O(n m + n^2 \log n)$.

Since Johnson's algorithm creates additional vertices, this implementation requires the user to provide a graph which is initialized with a vertex supplier.

In case the algorithm detects a negative weight cycle it will throw an exception of type NegativeCycleDetectedException which will contain the detected negative weight cycle.

  • Field Details

    • distance

      private double[][] distance

    • pred

      private E[][] pred

    • vertexIndices

      private Map<V,Integer> vertexIndices

    • comparator

      private final Comparator<Double> comparator

  • Constructor Details

    • JohnsonShortestPaths

      public JohnsonShortestPaths(Graph<V,E> graph)
      Construct a new instance.
      Parameters:
      graph - the input graph

    • JohnsonShortestPaths

      public JohnsonShortestPaths(Graph<V,E> graph, double epsilon)
      Construct a new instance.
      Parameters:
      graph - the input graph
      epsilon - tolerance when comparing floating point values

  • Method Details

    • getPath

      public GraphPath<V,E> getPath(V source, V sink)
      Get a shortest path from a source vertex to a sink vertex.
      Parameters:
      source - the source vertex
      sink - the target vertex
      Returns:
      a shortest path or null if no path exists
      Throws:
      IllegalArgumentException - in case the provided vertex factory creates vertices which are already in the original graph
      NegativeCycleDetectedException - in case a negative weight cycle is detected

    • 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>
      Overrides:
      getPathWeight in class BaseShortestPathAlgorithm<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
      Throws:
      IllegalArgumentException - in case the provided vertex factory creates vertices which are already in the original graph

    • 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>
      Overrides:
      getPaths in class BaseShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths
      Throws:
      IllegalArgumentException - in case the provided vertex factory creates vertices which are already in the original graph
      NegativeCycleDetectedException - in case a negative weight cycle is detected

    • run

      private void run()
      Executes the actual algorithm.

    • runWithPositiveEdgeWeights

      private void runWithPositiveEdgeWeights(Graph<V,E> g)
      Graph has no edges with negative weights. Only perform the last step of Johnson's algorithm: run Dijkstra's algorithm from every vertex.
      Parameters:
      g - the input graph

    • runWithNegativeEdgeWeights

      private void runWithNegativeEdgeWeights(Graph<V,E> g)
      Graph contains edges with negative weights. Transform the input graph, thereby ensuring that there are no edges with negative weights. Then run Dijkstra's algorithm for all vertices.
      Parameters:
      g - the input graph

    • computeVertexWeights

      private Map<V,Double> computeVertexWeights(Graph<V,E> g)
      Compute vertex weights for edge re-weighting using Bellman-Ford.
      Parameters:
      g - the input graph
      Returns:
      the vertex weights

    • computeVertexIndices

      private Map<V,Integer> computeVertexIndices(Graph<V,E> g)
      Compute a unique integer for each vertex of the graph
      Parameters:
      g - the graph
      Returns:
      a map with the result