程序包 edu.princeton.cs.algs4

类 FloydWarshall

java.lang.Object

edu.princeton.cs.algs4.FloydWarshall

public class FloydWarshall
extends java.lang.Object

The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted 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 Floyd-Warshall algorithm. The constructor takes time proportional to V³ in the worst case, where V is the number of vertices. Afterwards, the dist(), hasPath(), and hasNegativeCycle() methods take constant time; the path() and negativeCycle() method takes time proportional to the number of edges returned.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

构造器概要

构造器

构造器	说明
FloydWarshall(AdjMatrixEdgeWeightedDigraph G)	Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.

方法概要

修饰符和类型	方法	说明
double	dist(int s, int t)	Returns the length of a shortest path from vertex s to vertex t.
boolean	hasNegativeCycle()	Is there a negative cycle?
boolean	hasPath(int s, int t)	Is there a path from the vertex s to vertex t?
static void	main(java.lang.String[] args)	Unit tests the FloydWarshall data type.
java.lang.Iterable<DirectedEdge>	negativeCycle()	Returns a negative cycle, or null if there is no such cycle.
java.lang.Iterable<DirectedEdge>	path(int s, int t)	Returns a shortest path from vertex s to vertex t.

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

构造器详细资料

FloydWarshall

public FloydWarshall(AdjMatrixEdgeWeightedDigraph G)

Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G. If no such shortest path exists for some pair of vertices, it computes a negative cycle.

参数:

G - the edge-weighted digraph

方法详细资料

hasNegativeCycle

public boolean hasNegativeCycle()

Is there a negative cycle?

返回:

true if there is a negative cycle, and false otherwise

negativeCycle

public java.lang.Iterable<DirectedEdge> negativeCycle()

Returns a negative cycle, or null if there is no such cycle.

返回:

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 vertex s to vertex t?

参数:

s - the source vertex

t - the destination vertex

返回:

true if there is a path from vertex s to vertex t, and false otherwise

抛出:

java.lang.IllegalArgumentException - unless 0 <= s < V

java.lang.IllegalArgumentException - unless 0 <= t < V

dist

public double dist(int s,
                   int t)

Returns the length of a shortest path from vertex s to vertex t.

参数:

s - the source vertex

t - the destination vertex

返回:

the length of a shortest path from vertex s to vertex t; Double.POSITIVE_INFINITY if no such path

抛出:

java.lang.UnsupportedOperationException - if there is a negative cost cycle

java.lang.IllegalArgumentException - unless 0 <= v < V

path

public java.lang.Iterable<DirectedEdge> path(int s,
                                             int t)

Returns a shortest path from vertex s to vertex t.

参数:

s - the source vertex

t - the destination vertex

返回:

a shortest path from vertex s to vertex t as an iterable of edges, and null if no such path

抛出:

java.lang.UnsupportedOperationException - if there is a negative cost cycle

java.lang.IllegalArgumentException - unless 0 <= v < V

main

public static void main(java.lang.String[] args)

Unit tests the FloydWarshall data type.

参数:

args - the command-line arguments