com.mhhe.clrs2e
Class BellmanFord

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

public class BellmanFord

extends SingleSourceShortestPaths

Implementation of the Bellman-Ford algorithm on page 588 of Introduction to Algorithms, Second edition.

Field Summary

Fields inherited from class com.mhhe.clrs2e.SingleSourceShortestPaths

g, noNegWeightCycle

Constructor Summary

BellmanFord(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

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.

Methods inherited from class com.mhhe.clrs2e.SingleSourceShortestPaths

getShortestPathInfo, getShortestPathInfo, hasNoNegativeWeightCycle, initializeSingleSource, newShortestPathInfo

Methods inherited from class java.lang.Object

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

Constructor Detail

BellmanFord

public BellmanFord(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 SingleSourceShortestPaths.initializeSingleSource(com.mhhe.clrs2e.Vertex)'s job.)

Parameters:

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

Method Detail

computeShortestPaths

public 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. Also sets the instance variable noNegWeightCycle appropriately.

Specified by:

computeShortestPaths in class SingleSourceShortestPaths

Parameters:

s - The source vertex.