public class AcyclicSP extends Object
AcyclicSP
class represents a data type for solving the
single-source shortest paths problem in edge-weighted directed acyclic
graphs (DAGs). The edge weights can be positive, negative, or zero.
This implementation uses a topological-sort 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 edge-weighted digraph).
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^{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.
Constructor and Description |
---|
AcyclicSP(EdgeWeightedDigraph G,
int s)
Computes a shortest paths tree from
s to every other vertex in
the directed acyclic graph G . |
Modifier and Type | Method and Description |
---|---|
double |
distTo(int v)
Returns the length of a shortest path from the source vertex
s to vertex v . |
boolean |
hasPathTo(int v)
Is there a path from the source vertex
s to vertex v ? |
static void |
main(String[] args)
Unit tests the
AcyclicSP data type. |
Iterable<DirectedEdge> |
pathTo(int v)
Returns a shortest path from the source vertex
s to vertex v . |
public AcyclicSP(EdgeWeightedDigraph G, int s)
s
to every other vertex in
the directed acyclic graph G
.G
- the acyclic digraphs
- the source vertexIllegalArgumentException
- if the digraph is not acyclicIllegalArgumentException
- unless 0 <= s < V
public double distTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
;
Double.POSITIVE_INFINITY
if no such pathIllegalArgumentException
- unless 0 <= v < V
public boolean hasPathTo(int v)
s
to vertex v
?v
- the destination vertextrue
if there is a path from the source vertex
s
to vertex v
, and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<DirectedEdge> pathTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
as an iterable of edges, and null
if no such pathIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
AcyclicSP
data type.args
- the command-line arguments