Package dsa

Class Dijkstra

java.lang.Object

dsa.Dijkstra

All Implemented Interfaces:

Paths

public class Dijkstra
extends Object
implements Paths

An immutable data type to determine the shortest paths from a fixed source vertex to every other vertex in an edge-weighted digraph.

Constructor Summary

Constructors

Constructor	Description
Dijkstra(EdgeWeightedDiGraph G, int s)	Determines the shortest paths from the source vertex s to every other vertex in the edge-weighted digraph G.

Method Summary

Modifier and Type	Method	Description
double	distTo(int v)	Returns the shortest distance between a designated source vertex and vertex v, or infinity.
boolean	hasPathTo(int v)	Returns true if there is a path between a designated source vertex and vertex v, and false otherwise.
static void	main(String[] args)	Unit tests the data type.
Iterable<Integer>	pathTo(int v)	Returns a path between a designated source vertex and vertex v, or null.

Methods inherited from class java.lang.Object

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

Constructor Detail

Dijkstra

public Dijkstra(EdgeWeightedDiGraph G,
                int s)

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

Parameters:

G - the edge-weighted digraph.

s - the source vertex.

Method Detail

hasPathTo

public boolean hasPathTo(int v)

Description copied from interface: Paths

Returns true if there is a path between a designated source vertex and vertex v, and false otherwise.

Specified by:

hasPathTo in interface Paths

Parameters:

v - the vertex.

Returns:

true if there is a path between a designated source vertex and vertex v, and false otherwise.

pathTo

public Iterable<Integer> pathTo(int v)

Description copied from interface: Paths

Returns a path between a designated source vertex and vertex v, or null.

Specified by:

pathTo in interface Paths

Parameters:

v - the vertex.

Returns:

a path between a designated source vertex and vertex v, or null.

distTo

public double distTo(int v)

Description copied from interface: Paths

Returns the shortest distance between a designated source vertex and vertex v, or infinity.

Specified by:

distTo in interface Paths

Parameters:

v - the vertex.

Returns:

the shortest distance between a designated source vertex and vertex v, or infinity.

main

public static void main(String[] args)

Unit tests the data type.

Parameters:

args - the command-line arguments.