| DijkstraUndirectedSP Class |
The DijkstraUndirectedSP class represents a data type for solving the single-source shortest paths problem in edge-weighted graphs 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.
See for a version on edge-weighted digraphs.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class DijkstraUndirectedSP
The DijkstraUndirectedSP type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | DijkstraUndirectedSP |
Computes a shortest-paths tree from the source vertex s to every
other vertex in the edge-weighted graph G. |
Methods| Name | Description | |
|---|---|---|
| DistTo |
Returns the length of a shortest path between the source vertex s and
vertex v. |
| HasPathTo |
Returns true if there is a path between the source vertex s and
vertex v. |
 | MainTest |
Demo test the DijkstraUndirectedSP data type. |
| PathTo |
Returns a shortest path between the source vertex s and 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 DijkstraUndirectedSP implementation by the respective authors.
See Also