| DijkstraAllPairsSP Class |
The DijkstraAllPairsSP class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.
This implementation runs Dijkstra's algorithm from each vertex. The constructor takes time proportional to V (E log V) and uses space proprtional to V2, where V is the number of vertices and E is the number of edges. Afterwards, the Dist() and hasPath() methods take constant time and the Path() 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 DijkstraAllPairsSP
The DijkstraAllPairsSP type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | DijkstraAllPairsSP |
Computes a shortest paths tree from each vertex to to every other vertex in
the edge-weighted digraph G. |
Methods| Name | Description | |
|---|---|---|
| Dist |
Returns the length of a shortest path from vertex s to vertex t. |
| HasPath |
Is there a path from the vertex s to vertex t? |
| Path |
Returns a shortest path from vertex s to vertex t. |
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 DijkstraAllPairsSP implementation by the respective authors.
See Also