| AcyclicSP Class |
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.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class AcyclicSP
The AcyclicSP type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | AcyclicSP | Computes a shortest paths tree from s to every other vertex in
the directed acyclic graph G. |
Methods| Name | Description | |
|---|---|---|
| DistTo |
Returns the length of a shortest path from the source vertex s to vertex v. |
| HasPathTo |
Is there a path from the source vertex s to vertex v? |
 | MainTest |
Demo test the AcyclicSP data type. |
| PathTo |
Returns a shortest path from the source vertex s to vertex v. |
RemarksFor additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
This class is a C# port from the original Java class AcyclicSP implementation by the respective authors.
See Also