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

Class JohnsonShortestPaths<V,​E>

java.lang.Object
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 java.lang.Object
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.

Author:
Dimitrios Michail

  • Field Details

  • 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:
      java.lang.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>
      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:
      java.lang.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>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths
      Throws:
      java.lang.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

    • 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