Below is the syntax highlighted version of DijkstraSP.java
from §4.4 Shortest Paths.
/****************************************************************************** * Compilation: javac DijkstraSP.java * Execution: java DijkstraSP input.txt s * Dependencies: EdgeWeightedDigraph.java IndexMinPQ.java Stack.java DirectedEdge.java * Data files: https://algs4.cs.princeton.edu/44sp/tinyEWD.txt * https://algs4.cs.princeton.edu/44sp/mediumEWD.txt * https://algs4.cs.princeton.edu/44sp/largeEWD.txt * * Dijkstra's algorithm. Computes the shortest path tree. * Assumes all weights are non-negative. * * % java DijkstraSP tinyEWD.txt 0 * 0 to 0 (0.00) * 0 to 1 (1.05) 0->4 0.38 4->5 0.35 5->1 0.32 * 0 to 2 (0.26) 0->2 0.26 * 0 to 3 (0.99) 0->2 0.26 2->7 0.34 7->3 0.39 * 0 to 4 (0.38) 0->4 0.38 * 0 to 5 (0.73) 0->4 0.38 4->5 0.35 * 0 to 6 (1.51) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 * 0 to 7 (0.60) 0->2 0.26 2->7 0.34 * * % java DijkstraSP mediumEWD.txt 0 * 0 to 0 (0.00) * 0 to 1 (0.71) 0->44 0.06 44->93 0.07 ... 107->1 0.07 * 0 to 2 (0.65) 0->44 0.06 44->231 0.10 ... 42->2 0.11 * 0 to 3 (0.46) 0->97 0.08 97->248 0.09 ... 45->3 0.12 * 0 to 4 (0.42) 0->44 0.06 44->93 0.07 ... 77->4 0.11 * ... * ******************************************************************************/ /** * The {@code DijkstraSP} class represents a data type for solving the * single-source shortest paths problem in edge-weighted digraphs * where the edge weights are non-negative. * <p> * This implementation uses <em>Dijkstra's algorithm</em> with a * <em>binary heap</em>. The constructor takes * Θ(<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>) extra space (not including the * edge-weighted digraph). * <p> * This correctly computes shortest paths if all arithmetic performed is * without floating-point rounding error or arithmetic overflow. * This is the case if all edge weights are integers and if none of the * intermediate results exceeds 2<sup>52</sup>. Since all intermediate * results are sums of edge weights, they are bounded by <em>V C</em>, * where <em>V</em> is the number of vertices and <em>C</em> is the maximum * weight of any edge. * <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 DijkstraSP { private double[] distTo; // distTo[v] = distance of shortest s->v path private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private IndexMinPQ<Double> pq; // priority queue of vertices /** * Computes a shortest-paths tree from the source vertex {@code s} to every other * vertex in the edge-weighted digraph {@code G}. * * @param G the edge-weighted digraph * @param s the source vertex * @throws IllegalArgumentException if an edge weight is negative * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public DijkstraSP(EdgeWeightedDigraph G, int s) { for (DirectedEdge e : G.edges()) { if (e.weight() < 0) throw new IllegalArgumentException("edge " + e + " has negative weight"); } distTo = new double[G.V()]; edgeTo = new DirectedEdge[G.V()]; validateVertex(s); for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; distTo[s] = 0.0; // relax vertices in order of distance from s pq = new IndexMinPQ<Double>(G.V()); pq.insert(s, distTo[s]); while (!pq.isEmpty()) { int v = pq.delMin(); for (DirectedEdge e : G.adj(v)) relax(e); } // check optimality conditions assert check(G, s); } // relax edge e and update pq if changed private void relax(DirectedEdge e) { int v = e.from(), w = e.to(); if (distTo[w] > distTo[v] + e.weight()) { distTo[w] = distTo[v] + e.weight(); edgeTo[w] = e; if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); else pq.insert(w, distTo[w]); } } /** * Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}. * @param v the destination vertex * @return the length of a shortest path from the source vertex {@code s} to vertex {@code v}; * {@code Double.POSITIVE_INFINITY} if no such path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public double distTo(int v) { validateVertex(v); return distTo[v]; } /** * Returns true if there is a path from the source vertex {@code s} to vertex {@code v}. * * @param v the destination vertex * @return {@code true} if there is a path from the source vertex * {@code s} to vertex {@code v}; {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean hasPathTo(int v) { validateVertex(v); return distTo[v] < Double.POSITIVE_INFINITY; } /** * Returns a shortest path from the source vertex {@code s} to vertex {@code v}. * * @param v the destination vertex * @return a shortest path from the source vertex {@code s} to vertex {@code v} * as an iterable of edges, and {@code null} if no such path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public Iterable<DirectedEdge> pathTo(int v) { validateVertex(v); if (!hasPathTo(v)) return null; Stack<DirectedEdge> path = new Stack<DirectedEdge>(); for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { path.push(e); } return path; } // check optimality conditions: // (i) for all edges e: distTo[e.to()] <= distTo[e.from()] + e.weight() // (ii) for all edge e on the SPT: distTo[e.to()] == distTo[e.from()] + e.weight() private boolean check(EdgeWeightedDigraph G, int s) { // check that edge weights are non-negative for (DirectedEdge e : G.edges()) { if (e.weight() < 0) { System.err.println("negative edge weight detected"); return false; } } // check that distTo[v] and edgeTo[v] are consistent if (distTo[s] != 0.0 || edgeTo[s] != null) { System.err.println("distTo[s] and edgeTo[s] inconsistent"); return false; } for (int v = 0; v < G.V(); v++) { if (v == s) continue; if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) { System.err.println("distTo[] and edgeTo[] inconsistent"); return false; } } // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight() for (int v = 0; v < G.V(); v++) { for (DirectedEdge e : G.adj(v)) { int w = e.to(); if (distTo[v] + e.weight() < distTo[w]) { System.err.println("edge " + e + " not relaxed"); return false; } } } // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight() for (int w = 0; w < G.V(); w++) { if (edgeTo[w] == null) continue; DirectedEdge e = edgeTo[w]; int v = e.from(); if (w != e.to()) return false; if (distTo[v] + e.weight() != distTo[w]) { System.err.println("edge " + e + " on shortest path not tight"); return false; } } return true; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = distTo.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } /** * Unit tests the {@code DijkstraSP} data type. * * @param args the command-line arguments */ public static void main(String[] args) { In in = new In(args[0]); EdgeWeightedDigraph G = new EdgeWeightedDigraph(in); int s = Integer.parseInt(args[1]); // compute shortest paths DijkstraSP sp = new DijkstraSP(G, s); // print shortest path for (int t = 0; t < G.V(); t++) { if (sp.hasPathTo(t)) { StdOut.printf("%d to %d (%.2f) ", s, t, sp.distTo(t)); for (DirectedEdge e : sp.pathTo(t)) { StdOut.print(e + " "); } StdOut.println(); } else { StdOut.printf("%d to %d no path\n", s, t); } } } }