Class FloydWarshall
 Object

 edu.princeton.cs.algs4.FloydWarshall

public class FloydWarshall extends Object
TheFloydWarshall
class represents a data type for solving the allpairs shortest paths problem in edgeweighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path between every pair of vertices or a negative cycle.This implementation uses the FloydWarshall algorithm. The constructor takes Θ(V^{3}) time, where V is the number of vertices. Each instance method takes Θ(1) time. It uses Θ(V^{2}) extra space (not including the edgeweighted digraph).
This correctly computes shortest paths if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 2^{52}. Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum absolute value of any edge weight.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description FloydWarshall(AdjMatrixEdgeWeightedDigraph G)
Computes a shortest paths tree from each vertex to every other vertex in the edgeweighted digraphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
dist(int s, int t)
Returns the length of a shortest path from vertexs
to vertext
.boolean
hasNegativeCycle()
Is there a negative cycle?boolean
hasPath(int s, int t)
Is there a path from the vertexs
to vertext
?static void
main(String[] args)
Unit tests theFloydWarshall
data type.Iterable<DirectedEdge>
negativeCycle()
Returns a negative cycle, ornull
if there is no such cycle.Iterable<DirectedEdge>
path(int s, int t)
Returns a shortest path from vertexs
to vertext
.



Constructor Detail

FloydWarshall
public FloydWarshall(AdjMatrixEdgeWeightedDigraph G)
Computes a shortest paths tree from each vertex to every other vertex in the edgeweighted digraphG
. If no such shortest path exists for some pair of vertices, it computes a negative cycle. Parameters:
G
 the edgeweighted digraph


Method Detail

hasNegativeCycle
public boolean hasNegativeCycle()
Is there a negative cycle? Returns:
true
if there is a negative cycle, andfalse
otherwise

negativeCycle
public Iterable<DirectedEdge> negativeCycle()
Returns a negative cycle, ornull
if there is no such cycle. Returns:
 a negative cycle as an iterable of edges,
or
null
if there is no such cycle

hasPath
public boolean hasPath(int s, int t)
Is there a path from the vertexs
to vertext
? Parameters:
s
 the source vertext
 the destination vertex Returns:
true
if there is a path from vertexs
to vertext
, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= s < V
IllegalArgumentException
 unless0 <= t < V

dist
public double dist(int s, int t)
Returns the length of a shortest path from vertexs
to vertext
. Parameters:
s
 the source vertext
 the destination vertex Returns:
 the length of a shortest path from vertex
s
to vertext
;Double.POSITIVE_INFINITY
if no such path  Throws:
UnsupportedOperationException
 if there is a negative cost cycleIllegalArgumentException
 unless0 <= v < V

path
public Iterable<DirectedEdge> path(int s, int t)
Returns a shortest path from vertexs
to vertext
. Parameters:
s
 the source vertext
 the destination vertex Returns:
 a shortest path from vertex
s
to vertext
as an iterable of edges, andnull
if no such path  Throws:
UnsupportedOperationException
 if there is a negative cost cycleIllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theFloydWarshall
data type. Parameters:
args
 the commandline arguments

