Below is the syntax highlighted version of AcyclicLP.java
from §4.4 Shortest Paths.
/****************************************************************************** * Compilation: javac AcyclicLP.java * Execution: java AcyclicP V E * Dependencies: EdgeWeightedDigraph.java DirectedEdge.java Topological.java * Data files: https://algs4.cs.princeton.edu/44sp/tinyEWDAG.txt * * Computes longest paths in an edge-weighted acyclic digraph. * * Remark: should probably check that graph is a DAG before running * * % java AcyclicLP tinyEWDAG.txt 5 * 5 to 0 (2.44) 5->1 0.32 1->3 0.29 3->6 0.52 6->4 0.93 4->0 0.38 * 5 to 1 (0.32) 5->1 0.32 * 5 to 2 (2.77) 5->1 0.32 1->3 0.29 3->6 0.52 6->4 0.93 4->7 0.37 7->2 0.34 * 5 to 3 (0.61) 5->1 0.32 1->3 0.29 * 5 to 4 (2.06) 5->1 0.32 1->3 0.29 3->6 0.52 6->4 0.93 * 5 to 5 (0.00) * 5 to 6 (1.13) 5->1 0.32 1->3 0.29 3->6 0.52 * 5 to 7 (2.43) 5->1 0.32 1->3 0.29 3->6 0.52 6->4 0.93 4->7 0.37 * ******************************************************************************/ /** * The {@code AcyclicLP} class represents a data type for solving the * single-source longest paths problem in edge-weighted directed * acyclic graphs (DAGs). The edge weights can be positive, negative, or zero. * <p> * This implementation uses a topological-sort based algorithm. * The constructor takes Θ(<em>V</em> + <em>E</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 longest 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 * absolute value of any edge weight. * <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 AcyclicLP { private double[] distTo; // distTo[v] = distance of longest s->v path private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on longest s->v path /** * Computes a longest paths tree from {@code s} to every other vertex in * the directed acyclic graph {@code G}. * @param G the acyclic digraph * @param s the source vertex * @throws IllegalArgumentException if the digraph is not acyclic * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public AcyclicLP(EdgeWeightedDigraph G, int s) { distTo = new double[G.V()]; edgeTo = new DirectedEdge[G.V()]; validateVertex(s); for (int v = 0; v < G.V(); v++) distTo[v] = Double.NEGATIVE_INFINITY; distTo[s] = 0.0; // relax vertices in topological order Topological topological = new Topological(G); if (!topological.hasOrder()) throw new IllegalArgumentException("Digraph is not acyclic."); for (int v : topological.order()) { for (DirectedEdge e : G.adj(v)) relax(e); } } // relax edge e, but update if you find a *longer* path 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; } } /** * Returns the length of a longest path from the source vertex {@code s} to vertex {@code v}. * @param v the destination vertex * @return the length of a longest path from the source vertex {@code s} to vertex {@code v}; * {@code Double.NEGATIVE_INFINITY} if no such path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public double distTo(int v) { validateVertex(v); return distTo[v]; } /** * Is there 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}, and {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean hasPathTo(int v) { validateVertex(v); return distTo[v] > Double.NEGATIVE_INFINITY; } /** * Returns a longest path from the source vertex {@code s} to vertex {@code v}. * @param v the destination vertex * @return a longest 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; } // 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 AcyclicLP} data type. * * @param args the command-line arguments */ public static void main(String[] args) { In in = new In(args[0]); int s = Integer.parseInt(args[1]); EdgeWeightedDigraph G = new EdgeWeightedDigraph(in); AcyclicLP lp = new AcyclicLP(G, s); for (int v = 0; v < G.V(); v++) { if (lp.hasPathTo(v)) { StdOut.printf("%d to %d (%.2f) ", s, v, lp.distTo(v)); for (DirectedEdge e : lp.pathTo(v)) { StdOut.print(e + " "); } StdOut.println(); } else { StdOut.printf("%d to %d no path\n", s, v); } } } }