Package graph

Class ShortestPaths<Vertex,Edge>

java.lang.Object

graph.ShortestPaths<Vertex,Edge>

public class ShortestPaths<Vertex,Edge>
extends Object

This object computes and remembers shortest paths through a weighted, directed graph. Once shortest paths are computed from a specified source vertex, it allows querying the distance to arbitrary vertices and the best paths to arbitrary destination vertices.

Types Vertex and Edge are parameters, so their operations are supplied by a model object supplied to the constructor.

Constructor Summary

Constructors

Constructor	Description
ShortestPaths(WeightedDigraph<Vertex,Edge> graph)	Creates: a single-source shortest-path finder for a weighted graph.

Method Summary

Modifier and Type	Method	Description
List<Edge>	bestPath(Vertex target)	Returns: the best path from the source vertex to a given target vertex.
double	getDistance(Vertex v)	Returns: the distance from the source vertex to the given vertex.
void	singleSourceDistances(Vertex source)	Effect: Computes the best paths from a given source vertex, which can then be queried using bestPath().

Methods inherited from class java.lang.Object

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

Constructor Details

ShortestPaths

public ShortestPaths(WeightedDigraph<Vertex,Edge> graph)

Creates: a single-source shortest-path finder for a weighted graph.

Parameters:

graph - The model that supplies all graph operations.

Method Details

singleSourceDistances

public void singleSourceDistances(Vertex source)

Effect: Computes the best paths from a given source vertex, which can then be queried using bestPath().

getDistance

public double getDistance(Vertex v)

Returns: the distance from the source vertex to the given vertex. Checks: distances have been computed from a source vertex, and vertex v is reachable from that vertex.

bestPath

public List<Edge> bestPath(Vertex target)

Returns: the best path from the source vertex to a given target vertex. The path is represented as a list of edges. Requires: singleSourceDistances() has already been used to compute best paths.