Class DijkstraShortestPathsAlgorithm<V,​E extends GEdge<V>>

  • Type Parameters:
    V - the type of vertices
    E - the type of edges

    public class DijkstraShortestPathsAlgorithm<V,​E extends GEdge<V>>
    extends java.lang.Object
    Dijkstra's shortest-path algorithm

    This implementation computes the shortest paths between two vertices using Dijkstra's single-source shortest path finding algorithm. Any time a new source is given, it explores all destinations in the graph up to a maximum distance from the source. Thus, this implementation is best applied when many queries are anticipated from relatively few sources.

    • Constructor Detail

      • DijkstraShortestPathsAlgorithm

        public DijkstraShortestPathsAlgorithm​(GImplicitDirectedGraph<V,​E> graph)
        Use Dijkstra's algorithm on the given graph

        This constructor assumes the graph's edges are GWeightedEdges. If not, you will likely encounter a ClassCastException.

        Parameters:
        graph - the graph
      • DijkstraShortestPathsAlgorithm

        public DijkstraShortestPathsAlgorithm​(GImplicitDirectedGraph<V,​E> graph,
                                              double maxDistance)
        Use Dijkstra's algorithm on the given graph with the given maximum distance

        This constructor assumes the graph's edges are GWeightedEdges. If not, you will likely encounter a ClassCastException.

        Parameters:
        graph - the graph
        maxDistance - the maximum distance, or null for no maximum
      • DijkstraShortestPathsAlgorithm

        public DijkstraShortestPathsAlgorithm​(GImplicitDirectedGraph<V,​E> graph,
                                              GEdgeWeightMetric<E> metric)
        Use Dijstra's algorithm on the given graph with a custom edge weight metric
        Parameters:
        graph - the graph
        metric - the function to compute the weight of an edge
      • DijkstraShortestPathsAlgorithm

        public DijkstraShortestPathsAlgorithm​(GImplicitDirectedGraph<V,​E> graph,
                                              double maxDistance,
                                              GEdgeWeightMetric<E> metric)
        Use Dijstra's algorithm on the given graph with the given maximum distance and a custom edge weight metric
        Parameters:
        graph - the graph
        maxDistance - the maximum distance, or null for no maximum
        metric - the function to compute the weight of an edge
    • Method Detail

      • getDistancesFromSource

        public java.util.Map<V,​java.lang.Double> getDistancesFromSource​(V v)
        Compute the shortest distance to all reachable vertices from the given source
        Parameters:
        v - the source vertex
        Returns:
        a map of destinations to distances from the given source
      • computeOptimalPaths

        public java.util.Collection<java.util.Deque<E>> computeOptimalPaths​(V src,
                                                                            V dst)
        Compute the shortest paths from the given source to the given destination

        This implementation differs from typical implementations in that paths tied for the shortest distance are all returned. Others tend to choose one arbitrarily.

        Parameters:
        src - the source
        dst - the destination
        Returns:
        a collection of paths of shortest distance from source to destination