Class DijkstraShortestPath<V,​E>

  • All Implemented Interfaces:
    Distance<V>, ShortestPath<V,​E>

    public class DijkstraShortestPath<V,​E>
    extends DijkstraDistance<V,​E>
    implements ShortestPath<V,​E>

    Calculates distances and shortest paths using Dijkstra's single-source-shortest-path algorithm. This is a lightweight extension of DijkstraDistance that also stores path information, so that the shortest paths can be reconstructed.

    The elements in the maps returned by getIncomingEdgeMap are ordered (that is, returned by the iterator) by nondecreasing distance from source.

    See Also:
    DijkstraDistance
    • Constructor Summary

      Constructors 
      Constructor Description
      DijkstraShortestPath​(Graph<V,​E> g)
      Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.
      DijkstraShortestPath​(Graph<V,​E> g, boolean cached)
      Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.
      DijkstraShortestPath​(Graph<V,​E> g, com.google.common.base.Function<E,​? extends java.lang.Number> nev)
      Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges, which caches results locally.
      DijkstraShortestPath​(Graph<V,​E> g, com.google.common.base.Function<E,​? extends java.lang.Number> nev, boolean cached)
      Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges, which caches results locally if and only if cached is true.
    • Constructor Detail

      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> g,
                                    com.google.common.base.Function<E,​? extends java.lang.Number> nev,
                                    boolean cached)

        Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges, which caches results locally if and only if cached is true.

        Parameters:
        g - the graph on which distances will be calculated
        nev - the class responsible for returning weights for edges
        cached - specifies whether the results are to be cached
      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> g,
                                    com.google.common.base.Function<E,​? extends java.lang.Number> nev)

        Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges, which caches results locally.

        Parameters:
        g - the graph on which distances will be calculated
        nev - the class responsible for returning weights for edges
      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> g)

        Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.

        Parameters:
        g - the graph on which distances will be calculated
      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> g,
                                    boolean cached)

        Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.

        Parameters:
        g - the graph on which distances will be calculated
        cached - specifies whether the results are to be cached
    • Method Detail

      • getIncomingEdge

        public E getIncomingEdge​(V source,
                                 V target)

        Returns the last edge on a shortest path from source to target, or null if target is not reachable from source.

        If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException.

        Parameters:
        source - the vertex where the shortest path starts
        target - the vertex where the shortest path ends
        Returns:
        the last edge on a shortest path from source to target or null if target is not reachable from source
      • getIncomingEdgeMap

        public java.util.Map<V,​E> getIncomingEdgeMap​(V source)

        Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to the last edge on the shortest path from the source vertex. The map's iterator will return the elements in order of increasing distance from source.

        Specified by:
        getIncomingEdgeMap in interface ShortestPath<V,​E>
        Parameters:
        source - the vertex from which distances are measured
        Returns:
        a map from vertices to the last edge on the shortest path to that vertex starting from source
        See Also:
        DijkstraDistance.getDistanceMap(Object,int), DijkstraDistance.getDistance(Object,Object)
      • getPath

        public java.util.List<E> getPath​(V source,
                                         V target)
        Returns a List of the edges on the shortest path from source to target, in order of their occurrence on this path. If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException.
        Parameters:
        source - the starting vertex for the path to generate
        target - the ending vertex for the path to generate
        Returns:
        the edges on the shortest path from source to target, in order of their occurrence
      • getIncomingEdgeMap

        public java.util.LinkedHashMap<V,​E> getIncomingEdgeMap​(V source,
                                                                     int numDests)

        Returns a LinkedHashMap which maps each of the closest numDests vertices to the source vertex in the graph (including the source vertex) to the incoming edge along the path from that vertex. Throws an IllegalArgumentException if source is not in this instance's graph, or if numDests is either less than 1 or greater than the number of vertices in the graph.

        Parameters:
        source - the vertex from which distances are measured
        numDests - the number of vertices for which to measure distances
        Returns:
        a map from each of the closest numDests vertices to the last edge on the shortest path to that vertex starting from source
        See Also:
        getIncomingEdgeMap(Object), getPath(Object,Object)