Below is the syntax highlighted version of DijkstraAllPairsSP.java.
/****************************************************************************** * 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. * * % java DijkstraAllPairsSP tinyEWD.txt * ******************************************************************************/ 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 non-negative. * <p> * This implementation runs Dijkstra's algorithm from each vertex. * The constructor takes Θ(<em>V</em> (<em>E</em> log <em>V</em>)) time * in the worst case, where <em>V</em> is the number of vertices and * <em>E</em> is the number of edges. * Each instance method takes Θ(1) time. * It uses Θ(<em>V</em><sup>2</sup>) extra space (not including the * edge-weighted digraph). * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/44sp">Section 4.4</a> of * <i>Algorithms, 4th Edition</i> 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 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<DirectedEdge> 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)); } /** * Unit tests the {@code DijkstraAllPairsSP} data type. * * @param args the command-line arguments */ public static void main(String[] args) { // read edge-weighted digraph In in = new In(args[0]); EdgeWeightedDigraph G = new EdgeWeightedDigraph(in); // compute shortest paths between all pairs of vertices DijkstraAllPairsSP spt = new DijkstraAllPairsSP(G); // print all-pairs shortest path distances StdOut.printf(" "); for (int v = 0; v < G.V(); v++) { StdOut.printf("%6d ", v); } StdOut.println(); for (int v = 0; v < G.V(); v++) { StdOut.printf("%3d: ", v); for (int w = 0; w < G.V(); w++) { if (spt.hasPath(v, w)) StdOut.printf("%6.2f ", spt.dist(v, w)); else StdOut.printf(" Inf "); } StdOut.println(); } StdOut.println(); // print all-pairs shortest paths for (int v = 0; v < G.V(); v++) { for (int w = 0; w < G.V(); w++) { if (spt.hasPath(v, w)) { StdOut.printf("%d to %d (%5.2f) ", v, w, spt.dist(v, w)); for (DirectedEdge e : spt.path(v, w)) StdOut.print(e + " "); StdOut.println(); } else { StdOut.printf("%d to %d no path\n", v, w); } } } } } /****************************************************************************** * Copyright 2002-2022, 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. ******************************************************************************/