| DijkstraSP Class |
The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.
This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, 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 DijkstraSP
The DijkstraSP type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | DijkstraSP | Computes a shortest-paths tree from the source vertex s to every other
vertex in the edge-weighted digraph G. |
Methods| Name | Description | |
|---|---|---|
| DistTo |
Returns the length of a shortest path from the source vertex s to vertex v. |
| HasPathTo |
Returns true if there is a path from the source vertex s to vertex v. |
 | MainTest |
Demo test the DijkstraSP 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 DijkstraSP implementation by the respective authors.
See Also