A Practical Guide to Data Structures and Algorithms using Java

Abstract Weighted Graph and Weighted Graph Algorithms 945

WeightedGraph

The getNegativeWeightCycle method returns a positional collection that holds the edges in a nega-

tive weight cycle, or null if there is no negative weight cycle. This method uses buildCycleStartingAt

from the InTree class.

public PositionalCollection<E> getNegativeWeightCycle() {

if (hasNegativeWeightCycle())

return get(cycleStart).buildCycleStartingAt(cycleStart);

return null;

}

The getInTreeForSource method takes source, the desired source vertex. It returns a shortest path

tree for the given source vertex.

public InTree<V, E> getInTreeForSource(V source) {

return get(source);

}

Finally ...