程序包 edu.princeton.cs.algs4

类 BellmanFordSP

java.lang.Object

edu.princeton.cs.algs4.BellmanFordSP

public class BellmanFordSP
extends java.lang.Object

The BellmanFordSP class represents a data type for solving the single-source 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 from the source vertex s to every other vertex or a negative cycle reachable from the source vertex.

This implementation uses the Bellman-Ford-Moore algorithm. The constructor takes time proportional to V (V + E) in the worst case, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int), hasNegativeCycle takes constant time; each call to pathTo(int) and negativeCycle() takes time proportional to length of the path returned.

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

构造器概要

构造器

构造器	说明
BellmanFordSP(EdgeWeightedDigraph G, int s)	Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.

方法概要

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

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

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

构造器详细资料

BellmanFordSP

public BellmanFordSP(EdgeWeightedDigraph G,
                     int s)

Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.

参数:

G - the acyclic digraph

s - the source vertex

抛出:

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

方法详细资料

hasNegativeCycle

public boolean hasNegativeCycle()

Is there a negative cycle reachable from the source vertex s?

返回:

true if there is a negative cycle reachable from the source vertex s, and false otherwise

negativeCycle

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

Returns a negative cycle reachable from the source vertex s, or null if there is no such cycle.

返回:

a negative cycle reachable from the soruce vertex s as an iterable of edges, and null if there is no such cycle

distTo

public double distTo(int v)

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

参数:

v - the destination vertex

返回:

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

抛出:

java.lang.UnsupportedOperationException - if there is a negative cost cycle reachable from the source vertex s

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

hasPathTo

public boolean hasPathTo(int v)

Is there a path from the source s to vertex v?

参数:

v - the destination vertex

返回:

true if there is a path from the source vertex s to vertex v, and false otherwise

抛出:

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

pathTo

public java.lang.Iterable<DirectedEdge> pathTo(int v)

Returns a shortest path from the source s to vertex v.

参数:

v - the destination vertex

返回:

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

抛出:

java.lang.UnsupportedOperationException - if there is a negative cost cycle reachable from the source vertex s

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

main

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

Unit tests the BellmanFordSP data type.

参数:

args - the command-line arguments