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

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

      • distance

        private double[][] distance

      • pred

        private E[][] pred

      • vertexIndices

        private java.util.Map<V,​java.lang.Integer> vertexIndices

      • comparator

        private final java.util.Comparator<java.lang.Double> comparator

    • Constructor Detail

      • 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 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:
        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>
        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:
        java.lang.IllegalArgumentException - in case the provided vertex factory creates vertices which are already in the original graph

      • 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

      • computeVertexIndices

        private java.util.Map<V,​java.lang.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