程序包 edu.princeton.cs.algs4

类 DijkstraAllPairsSP

java.lang.Object

edu.princeton.cs.algs4.DijkstraAllPairsSP

public class DijkstraAllPairsSP
extends java.lang.Object

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 V², 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.

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

构造器概要

构造器

构造器	说明
DijkstraAllPairsSP(EdgeWeightedDigraph 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	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 DijkstraAllPairsSP data type.
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

构造器详细资料

DijkstraAllPairsSP

public DijkstraAllPairsSP(EdgeWeightedDigraph G)

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

参数:

G - the edge-weighted digraph

抛出:

java.lang.IllegalArgumentException - if an edge weight is negative

java.lang.IllegalArgumentException - unless 0 <= s < 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.IllegalArgumentException - unless 0 <= s < V

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

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.IllegalArgumentException - unless 0 <= s < V

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

main

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

Unit tests the DijkstraAllPairsSP data type.

参数:

args - the command-line arguments