com.mhhe.clrs2e
Class DAGShortestPaths

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

public class DAGShortestPaths

extends SingleSourceShortestPaths

Implementation of DAG-Shortest-Paths algorithm on page 592 of Introduction to Algorithms, Second edition.

Field Summary

Fields inherited from class com.mhhe.clrs2e.SingleSourceShortestPaths

g, noNegWeightCycle

Constructor Summary

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

DAGShortestPaths

public DAGShortestPaths(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.

Specified by:

computeShortestPaths in class SingleSourceShortestPaths

Parameters:

s - The source vertex.