程序包 edu.princeton.cs.algs4

类 DijkstraSP

java.lang.Object

edu.princeton.cs.algs4.DijkstraSP

public class DijkstraSP
extends java.lang.Object

The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.

This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int) takes constant time; each call to pathTo(int) 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.

构造器概要

构造器

构造器	说明
DijkstraSP(EdgeWeightedDigraph G, int s)	Computes a shortest-paths tree from the source vertex 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	hasPathTo(int v)	Returns true if there is a path from the source vertex s to vertex v.
static void	main(java.lang.String[] args)	Unit tests the DijkstraSP data type.
java.lang.Iterable<DirectedEdge>	pathTo(int v)	Returns a shortest path from the source vertex s to vertex v.

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

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

构造器详细资料

DijkstraSP

public DijkstraSP(EdgeWeightedDigraph G,
                  int s)

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

参数:

G - the edge-weighted digraph

s - the source vertex

抛出:

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

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

方法详细资料

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

hasPathTo

public boolean hasPathTo(int v)

Returns true if there is a path from the source vertex s to vertex v.

参数:

v - the destination vertex

返回:

true if there is a path from the source vertex s to vertex v; 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 vertex s to vertex v.

参数:

v - the destination vertex

返回:

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

抛出:

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

main

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

Unit tests the DijkstraSP data type.

参数:

args - the command-line arguments