/******************************************************************************
 *  Compilation:  javac DijkstraAllPairsSP.java
 *  Execution:    none
 *  Dependencies: EdgeWeightedDigraph.java Dijkstra.java
 *
 *  Dijkstra's algorithm run from each vertex. 
 *  Takes time proportional to E V log V and space proportional to EV.
 *
 ******************************************************************************/

package edu.princeton.cs.algs4;

/**
 *  The {@code DijkstraAllPairsSP} class represents a data type for solving the
 *  all-pairs shortest paths problem in edge-weighted digraphs
 *  where the edge weights are nonnegative.
 *  

* This implementation runs Dijkstra's algorithm from each vertex. * The constructor takes time proportional to V (E log V) * and uses space proprtional to V2, * where V is the number of vertices and E is the number of edges. * Afterwards, the {@code dist()} and {@code hasPath()} methods take * constant time and the {@code path()} method takes time proportional to the * number of edges in the shortest path returned. *

* For additional documentation, * see Section 4.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class DijkstraAllPairsSP { private DijkstraSP[] all; /** * Computes a shortest paths tree from each vertex to to every other vertex in * the edge-weighted digraph {@code G}. * @param G the edge-weighted digraph * @throws IllegalArgumentException if an edge weight is negative * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public DijkstraAllPairsSP(EdgeWeightedDigraph G) { all = new DijkstraSP[G.V()]; for (int v = 0; v < G.V(); v++) all[v] = new DijkstraSP(G, v); } /** * Returns a shortest path from vertex {@code s} to vertex {@code t}. * @param s the source vertex * @param t the destination vertex * @return a shortest path from vertex {@code s} to vertex {@code t} * as an iterable of edges, and {@code null} if no such path * @throws IllegalArgumentException unless {@code 0 <= s < V} * @throws IllegalArgumentException unless {@code 0 <= t < V} */ public Iterable path(int s, int t) { validateVertex(s); validateVertex(t); return all[s].pathTo(t); } /** * Is there a path from the vertex {@code s} to vertex {@code t}? * @param s the source vertex * @param t the destination vertex * @return {@code true} if there is a path from vertex {@code s} * to vertex {@code t}, and {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= s < V} * @throws IllegalArgumentException unless {@code 0 <= t < V} */ public boolean hasPath(int s, int t) { validateVertex(s); validateVertex(t); return dist(s, t) < Double.POSITIVE_INFINITY; } /** * Returns the length of a shortest path from vertex {@code s} to vertex {@code t}. * @param s the source vertex * @param t the destination vertex * @return the length of a shortest path from vertex {@code s} to vertex {@code t}; * {@code Double.POSITIVE_INFINITY} if no such path * @throws IllegalArgumentException unless {@code 0 <= s < V} * @throws IllegalArgumentException unless {@code 0 <= t < V} */ public double dist(int s, int t) { validateVertex(s); validateVertex(t); return all[s].distTo(t); } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = all.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } } /****************************************************************************** * Copyright 2002-2018, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/

Ads help maintain this website.