edu.princeton.cs.algs4

## Class AcyclicSP

• Object
• edu.princeton.cs.algs4.AcyclicSP

• ```public class AcyclicSP
extends Object```
The `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. Afterwards, the `distTo()` and `hasPathTo()` methods take constant time and the `pathTo()` method 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.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
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`.
• ### Method Summary

Methods
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`.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### AcyclicSP

```public AcyclicSP(EdgeWeightedDigraph G,
int s)```
Computes a shortest paths tree from `s` to every other vertex in the directed acyclic graph `G`.
Parameters:
`G` - the acyclic digraph
`s` - the source vertex
Throws:
`IllegalArgumentException` - if the digraph is not acyclic
`IllegalArgumentException` - unless `0 <= s < V`
• ### Method Detail

• #### distTo

`public double distTo(int v)`
Returns the length of a shortest path from the source vertex `s` to vertex `v`.
Parameters:
`v` - the destination vertex
Returns:
the length of a shortest path from the source vertex `s` to vertex `v`; `Double.POSITIVE_INFINITY` if no such path
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### hasPathTo

`public boolean hasPathTo(int v)`
Is there a path from the source vertex `s` to vertex `v`?
Parameters:
`v` - the destination vertex
Returns:
`true` if there is a path from the source vertex `s` to vertex `v`, and `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### pathTo

`public Iterable<DirectedEdge> pathTo(int v)`
Returns a shortest path from the source vertex `s` to vertex `v`.
Parameters:
`v` - the destination vertex
Returns:
a shortest path from the source vertex `s` to vertex `v` as an iterable of edges, and `null` if no such path
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### main

`public static void main(String[] args)`
Unit tests the `AcyclicSP` data type.
Parameters:
`args` - the command-line arguments