public class DijkstraAllPairsSP extends Object
DijkstraAllPairsSPclass 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.
hasPath() methods take
constant time and the
path() 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.
|Constructor and Description|
Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph
|Modifier and Type||Method and Description|
Returns the length of a shortest path from vertex
Is there a path from the vertex
Returns a shortest path from vertex
public DijkstraAllPairsSP(EdgeWeightedDigraph G)
public Iterable<DirectedEdge> path(int s, int t)
public boolean hasPath(int s, int t)
public double dist(int s, int t)