com.mhhe.clrs2e
Class Johnson

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

public class Johnson

extends java.lang.Object

Class to implement Johnson's all-pairs shortest-paths algorithm on page 639 of Introduction to Algorithms, Second edition.

Field Summary

private com.mhhe.clrs2e.WeightedAdjacencyListGraph	g The weighted, directed graph.
private 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 Johnson's algorithm.

Constructor Summary

Johnson(com.mhhe.clrs2e.WeightedAdjacencyListGraph theGraph)
Initializes the instance variables, except for allocating the acutal ShortestPathInfo objects in spInfo.

Method Summary

void	computeShortestPaths() Computes all-pairs shortest paths using Johnson's algorithm.
com.mhhe.clrs2e.ShortestPathInfo	getShortestPathInfo(int u, int v) Returns a reference to the ShortestPathInfo object for a given pair of vertices.
com.mhhe.clrs2e.ShortestPathInfo	getShortestPathInfo(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v) Returns a reference to the ShortestPathInfo object for a given pair of vertices.
boolean	hasNoNegativeWeightCycle() After running computeShortestPaths, returns true if no negative-weight cycles were detected, false if a negative-weight cycle was detected.

Methods inherited from class java.lang.Object

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

Field Detail

g

private com.mhhe.clrs2e.WeightedAdjacencyListGraph g

The weighted, directed graph.

noNegWeightCycle

private 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 Johnson's algorithm. The ShortestPathInfo object in spInfo[u][v] contains the shortest-path weight from u to v, where u and v are vertex indices, along with v's predecessor on a shortest path from u. You can query this information by calling methods of the ShortestPathInfo class.

Constructor Detail

Johnson

public Johnson(com.mhhe.clrs2e.WeightedAdjacencyListGraph theGraph)

Initializes the instance variables, except for allocating the acutal ShortestPathInfo objects in spInfo.

Parameters:

theGraph - The weighted, directed graph.

Method Detail

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 u,
                                                            com.mhhe.clrs2e.Vertex v)

Returns a reference to the ShortestPathInfo object for a given pair of vertices.

Parameters:

u - One of the vertices.

v - The other vertex.

getShortestPathInfo

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

Returns a reference to the ShortestPathInfo object for a given pair of vertices.

Parameters:

u - The index of one of the vertices.

v - The index of the other vertex.

computeShortestPaths

public void computeShortestPaths()

Computes all-pairs shortest paths using Johnson's algorithm. The results are the ShortestPathInfo objects referenced by the spInfo array, along with the noNegWeightCycle flag.