Package org.jgrapht.alg.shortestpath

Class DijkstraShortestPath<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    ShortestPathAlgorithm<V,​E>
    public final class DijkstraShortestPath<V,​E>
extends Object
    An implementation of Dijkstra's shortest path algorithm using a pairing heap by default. A custom heap implementation can by specified during the construction time.
    Author:
    John V. Sichi

    • Field Detail

      • GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

        protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
        Error message for reporting the existence of a negative-weight cycle.
        See Also:
        Constant Field Values

      • GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

        protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
        Error message for reporting that a source vertex is missing.
        See Also:
        Constant Field Values

      • GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

        protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
        Error message for reporting that a sink vertex is missing.
        See Also:
        Constant Field Values

      • graph

        protected final Graph<V,​E> graph
        The underlying graph.

    • Constructor Detail

      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> graph)
        Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation.
        Parameters:
        graph - the graph

      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> graph,
                            double radius)
        Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation.
        Parameters:
        graph - the graph
        radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search

      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> graph,
                            Supplier<org.jheaps.AddressableHeap<Double,​Pair<V,​E>>> heapSupplier)
        Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use the heap supplied by the heapSupplier
        Parameters:
        graph - the graph
        heapSupplier - supplier of the preferable heap implementation

      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> graph,
                            double radius,
                            Supplier<org.jheaps.AddressableHeap<Double,​Pair<V,​E>>> heapSupplier)
        Constructs a new instance of the algorithm for a given graph.
        Parameters:
        graph - the graph
        radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search
        heapSupplier - supplier of the preferable heap implementation

    • Method Detail

      • findPathBetween

        public static <V,​E> GraphPath<V,​E> findPathBetween​(Graph<V,​E> graph,
                                                               V source,
                                                               V sink)
        Find a path between two vertices. For a more advanced search (e.g. limited by radius or using another heap), use the constructor instead.
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        graph - the graph to be searched
        source - the vertex at which the path should start
        sink - the vertex at which the path should end
        Returns:
        a shortest path, or null if no path exists

      • 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

      • getPaths

        public ShortestPathAlgorithm.SingleSourcePaths<V,​E> getPaths​(V source)
        Compute all shortest paths starting from a single source vertex.

        Note that in the case of Dijkstra's algorithm it is more efficient to compute all single-source shortest paths using this method than repeatedly invoking getPath(Object, Object) for the same source but different sink vertex.

        Specified by:
        getPaths in interface ShortestPathAlgorithm<V,​E>
        Parameters:
        source - the source vertex
        Returns:
        the shortest paths

      • 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

      • 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