Class DijkstraAllPairsSP


  • public class DijkstraAllPairsSP
    extends Object
    The DijkstraAllPairsSP class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs where the edge weights are non-negative.

    This implementation runs Dijkstra's algorithm from each vertex. The constructor takes Θ(V (E log V)) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V2) extra space (not including the edge-weighted digraph).

    For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

    • Method Detail

      • path

        public Iterable<DirectedEdge> path​(int s,
                                           int t)
        Returns a shortest path from vertex s to vertex t.
        Parameters:
        s - the source vertex
        t - the destination vertex
        Returns:
        a shortest path from vertex s to vertex t as an iterable of edges, and null if no such path
        Throws:
        IllegalArgumentException - unless 0 <= s < V
        IllegalArgumentException - unless 0 <= t < V
      • hasPath

        public boolean hasPath​(int s,
                               int t)
        Is there a path from the vertex s to vertex t?
        Parameters:
        s - the source vertex
        t - the destination vertex
        Returns:
        true if there is a path from vertex s to vertex t, and false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= s < V
        IllegalArgumentException - unless 0 <= t < V
      • dist

        public double dist​(int s,
                           int t)
        Returns the length of a shortest path from vertex s to vertex t.
        Parameters:
        s - the source vertex
        t - the destination vertex
        Returns:
        the length of a shortest path from vertex s to vertex t; Double.POSITIVE_INFINITY if no such path
        Throws:
        IllegalArgumentException - unless 0 <= s < V
        IllegalArgumentException - unless 0 <= t < V
      • main

        public static void main​(String[] args)
        Unit tests the DijkstraAllPairsSP data type.
        Parameters:
        args - the command-line arguments