Class AcyclicSP
 Object

 edu.princeton.cs.algs4.AcyclicSP

public class AcyclicSP extends Object
TheAcyclicSP
class represents a data type for solving the singlesource shortest paths problem in edgeweighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.This implementation uses a topologicalsort based algorithm. The constructor takes Θ(V + E) 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 Θ(V) extra space (not including the edgeweighted digraph).
This correctly computes shortest paths if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 2^{52}. Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum absolute value of any edge weight.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description AcyclicSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree froms
to every other vertex in the directed acyclic graphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
distTo(int v)
Returns the length of a shortest path from the source vertexs
to vertexv
.boolean
hasPathTo(int v)
Is there a path from the source vertexs
to vertexv
?static void
main(String[] args)
Unit tests theAcyclicSP
data type.Iterable<DirectedEdge>
pathTo(int v)
Returns a shortest path from the source vertexs
to vertexv
.



Constructor Detail

AcyclicSP
public AcyclicSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree froms
to every other vertex in the directed acyclic graphG
. Parameters:
G
 the acyclic digraphs
 the source vertex Throws:
IllegalArgumentException
 if the digraph is not acyclicIllegalArgumentException
 unless0 <= s < V


Method Detail

distTo
public double distTo(int v)
Returns the length of a shortest path from the source vertexs
to vertexv
. Parameters:
v
 the destination vertex Returns:
 the length of a shortest path from the source vertex
s
to vertexv
;Double.POSITIVE_INFINITY
if no such path  Throws:
IllegalArgumentException
 unless0 <= v < V

hasPathTo
public boolean hasPathTo(int v)
Is there a path from the source vertexs
to vertexv
? Parameters:
v
 the destination vertex Returns:
true
if there is a path from the source vertexs
to vertexv
, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

pathTo
public Iterable<DirectedEdge> pathTo(int v)
Returns a shortest path from the source vertexs
to vertexv
. Parameters:
v
 the destination vertex Returns:
 a shortest path from the source vertex
s
to vertexv
as an iterable of edges, andnull
if no such path  Throws:
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theAcyclicSP
data type. Parameters:
args
 the commandline arguments

