- java.lang.Object
-
- org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
-
- org.jgrapht.alg.shortestpath.JohnsonShortestPaths<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
JohnsonShortestPaths.JohnsonSingleSourcePaths
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Comparator<java.lang.Double>
comparator
private double[][]
distance
private E[][]
pred
private java.util.Map<V,java.lang.Integer>
vertexIndices
-
Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
graph, GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
-
-
Constructor Summary
Constructors Constructor Description JohnsonShortestPaths(Graph<V,E> graph)
Construct a new instance.JohnsonShortestPaths(Graph<V,E> graph, double epsilon)
Construct a new instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private java.util.Map<V,java.lang.Integer>
computeVertexIndices(Graph<V,E> g)
Compute a unique integer for each vertex of the graphprivate java.util.Map<V,java.lang.Double>
computeVertexWeights(Graph<V,E> g)
Compute vertex weights for edge re-weighting using Bellman-Ford.GraphPath<V,E>
getPath(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.ShortestPathAlgorithm.SingleSourcePaths<V,E>
getPaths(V source)
Compute all shortest paths starting from a single source vertex.double
getPathWeight(V source, V sink)
Get the weight of the shortest path from a source vertex to a sink vertex.private void
run()
Executes the actual algorithm.private void
runWithNegativeEdgeWeights(Graph<V,E> g)
Graph contains edges with negative weights.private void
runWithPositiveEdgeWeights(Graph<V,E> g)
Graph has no edges with negative weights.-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath
-
-
-
-
Method Detail
-
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 vertexsink
- 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 graphNegativeCycleDetectedException
- 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. ReturnsDouble.POSITIVE_INFINITY
if no path exists.- Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,E>
- Overrides:
getPathWeight
in classBaseShortestPathAlgorithm<V,E>
- Parameters:
source
- the source vertexsink
- 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 interfaceShortestPathAlgorithm<V,E>
- Overrides:
getPaths
in classBaseShortestPathAlgorithm<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 graphNegativeCycleDetectedException
- 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 java.util.Map<V,java.lang.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
-
-