Package org.graph4j.shortestpath

Class JohnsonShortestPath

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.shortestpath.JohnsonShortestPath
All Implemented Interfaces:
AllPairsShortestPath
public class JohnsonShortestPath extends GraphAlgorithm implements AllPairsShortestPath
Johnson's algorithm finds the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using 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.

The complexity of the algorithm is O(nmlogn), given by the Dijkstra's algorithm implemented with a binary heap, which is repeated for every vertex. It is best suited for sparse graphs. In case of dense graphs FloydWarshallShortestPath algorithm may perform better.

Author:
Cristian Frăsinaru, Cristian Ivan
See Also:

  • Constructor Details

    • JohnsonShortestPath

      public JohnsonShortestPath(Graph graph)

  • Method Details

    • findPath

      public Path findPath(int source, int target)
      Description copied from interface: AllPairsShortestPath
      Returns the shortest path between source and target. On the first invocation of this method, it computes shortest paths between any two vertices of the graph, then it returns the requested one. All the shortest paths are stored for later retrieval, so subsequent invocations will return the already computed paths.
      Specified by:
      findPath in interface AllPairsShortestPath
      Parameters:
      source - the number of the source vertex.
      target - the number of the target vertex.
      Returns:
      the shortest path from the source to the target, or null if no path exists.

    • getPathWeight

      public double getPathWeight(int source, int target)
      Specified by:
      getPathWeight in interface AllPairsShortestPath
      Parameters:
      source - the number of the source vertex.
      target - the number of the target vertex.
      Returns:
      the weight of the shortest path from the source to the target, or Double.POSTIVE_INFINITY if no path exists.

    • getPathWeights

      public double[][] getPathWeights()
      Returns a matrix containing the weights of the shortest paths for every pair of vertices. This implementation is multi-threaded.
      Specified by:
      getPathWeights in interface AllPairsShortestPath
      Returns:
      a matrix containing the weights of the shortest paths for every pair of vertices.