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 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 VertexFactory. Since the graph already contains vertices, care must be taken so that the provided vertex factory does not return nodes that are already contained in the original input graph.

Since:

February 2017

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,E>

Field Summary

Fields

Modifier and Type	Field and Description
protected Graph<V,E>	graph The underlying graph.

Constructor Summary

Constructors

Constructor and Description
JohnsonShortestPaths(Graph<V,E> graph, Class<? extends V> vertexClass) Construct a new instance.
JohnsonShortestPaths(Graph<V,E> graph, VertexFactory<V> vertexFactory) Construct a new instance.
JohnsonShortestPaths(Graph<V,E> graph, VertexFactory<V> vertexFactory, double epsilon) Construct a new instance.

Method Summary

Modifier and Type	Method and Description
protected GraphPath<V,E>	createEmptyPath(V source, V sink) Create an empty path.
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graph

protected final Graph<V,E> graph

The underlying graph.

Constructor Detail

JohnsonShortestPaths

public JohnsonShortestPaths(Graph<V,E> graph,
                            Class<? extends V> vertexClass)

Construct a new instance.

Parameters:

graph - the input graph

vertexClass - the graph vertex class

JohnsonShortestPaths

public JohnsonShortestPaths(Graph<V,E> graph,
                            VertexFactory<V> vertexFactory)

Construct a new instance.

Parameters:

graph - the input graph

vertexFactory - the vertex factory of the graph

JohnsonShortestPaths

public JohnsonShortestPaths(Graph<V,E> graph,
                            VertexFactory<V> vertexFactory,
                            double epsilon)

Construct a new instance.

Parameters:

graph - the input graph

vertexFactory - the vertex factory of the graph

epsilon - tolerance when comparing floating point values

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 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

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:

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:

IllegalArgumentException - in case the provided vertex factory creates vertices which are already in the original graph

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