com.mhhe.clrs2e
Class SingleSourceShortestPaths

java.lang.Object
  |
  +--com.mhhe.clrs2e.SingleSourceShortestPaths

Direct Known Subclasses:

BellmanFord, DAGShortestPaths, Dijkstra

public abstract class SingleSourceShortestPaths

extends java.lang.Object

Abstract class for computing single-source shortest paths. Defines methods for algorithms in Chapter 24 of Introduction to Algorithms, Second edition.

Field Summary

protected com.mhhe.clrs2e.WeightedAdjacencyListGraph	g The graph for which we are computing single-source shortest paths.
protected boolean	noNegWeightCycle true if no negative-weight cycles were detected, false if a negative-weight cycle was detected.
private com.mhhe.clrs2e.ShortestPathInfo[]	spInfo The result of running a single-source shortest-paths algorithm.

Constructor Summary

protected

SingleSourceShortestPaths(com.mhhe.clrs2e.WeightedAdjacencyListGraph theGraph) Sets up the instance variables, including allocation of the spInfo array but not allocation of the ShortestPathInfo objects referenced by the array.

Method Summary

abstract void	computeShortestPaths(com.mhhe.clrs2e.Vertex s) Computes single-source shortest paths from a given source vertex, filling in weights and predecessors in the spInfo array.
com.mhhe.clrs2e.ShortestPathInfo	getShortestPathInfo(int v) Returns a reference to the ShortestPathInfo object for a given vertex.
com.mhhe.clrs2e.ShortestPathInfo	getShortestPathInfo(com.mhhe.clrs2e.Vertex v) Returns a reference to the ShortestPathInfo object for a given vertex.
boolean	hasNoNegativeWeightCycle() After running computeShortestPaths, returns true if no negative-weight cycles were detected, false if a negative-weight cycle was detected.
void	initializeSingleSource(com.mhhe.clrs2e.Vertex s) Initializes a single-source shortest-paths algorithm.
protected com.mhhe.clrs2e.ShortestPathInfo	newShortestPathInfo() Returns a new ShortestPathInfo object.

Methods inherited from class java.lang.Object

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

Field Detail

g

protected com.mhhe.clrs2e.WeightedAdjacencyListGraph g

The graph for which we are computing single-source shortest paths.

noNegWeightCycle

protected boolean noNegWeightCycle

true if no negative-weight cycles were detected, false if a negative-weight cycle was detected.

spInfo

private com.mhhe.clrs2e.ShortestPathInfo[] spInfo

The result of running a single-source shortest-paths algorithm. Each object in this array corresponds to a vertex of the graph, and you can query its answers by calling methods of the ShortestPathInfo class.

Constructor Detail

SingleSourceShortestPaths

protected SingleSourceShortestPaths(com.mhhe.clrs2e.WeightedAdjacencyListGraph theGraph)

Sets up the instance variables, including allocation of the spInfo array but not allocation of the ShortestPathInfo objects referenced by the array. (That's initializeSingleSource(com.mhhe.clrs2e.Vertex)'s job.)

Parameters:

theGraph - The graph for which we are computing single-source shortest paths.

Method Detail

computeShortestPaths

public abstract void computeShortestPaths(com.mhhe.clrs2e.Vertex s)

Computes single-source shortest paths from a given source vertex, filling in weights and predecessors in the spInfo array.

Parameters:

s - The source vertex.

initializeSingleSource

public void initializeSingleSource(com.mhhe.clrs2e.Vertex s)

Initializes a single-source shortest-paths algorithm.

Parameters:

s - The source vertex.

newShortestPathInfo

protected com.mhhe.clrs2e.ShortestPathInfo newShortestPathInfo()

Returns a new ShortestPathInfo object. This method may be overridden in subclasses.

hasNoNegativeWeightCycle

public boolean hasNoNegativeWeightCycle()

After running computeShortestPaths, returns true if no negative-weight cycles were detected, false if a negative-weight cycle was detected.

getShortestPathInfo

public com.mhhe.clrs2e.ShortestPathInfo getShortestPathInfo(com.mhhe.clrs2e.Vertex v)

Returns a reference to the ShortestPathInfo object for a given vertex.

Parameters:

v - The vertex for which the corresponding ShortestPathInfo is returned.

getShortestPathInfo

public com.mhhe.clrs2e.ShortestPathInfo getShortestPathInfo(int v)

Returns a reference to the ShortestPathInfo object for a given vertex.

Parameters:

v - The index of the vertex for which the corresponding ShortestPathInfo is returned.