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 time proportional to V + E,
where V is the number of vertices and E is the number of edges.
Each call to distTo(int)
and hasPathTo(int)
takes constant time;
each call to pathTo(int)
takes time proportional to the number of
edges in the shortest path returned.
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