com.codemelon.graph.algorithm.path

Class BellmanFord<E extends EdgeWeightData,V extends DirectedEdgeDataVertex<E> & ShortestPathVertex<E>>

java.lang.Object

com.codemelon.graph.algorithm.path.BellmanFord<E,V>

public class BellmanFord<E extends EdgeWeightData,V extends DirectedEdgeDataVertex<E> & ShortestPathVertex<E>>
extends java.lang.Object

Implementation of Bellman-Ford algorithm following CLRS, pp. 651ff.

Constructor Summary

Constructors

Constructor and Description
BellmanFord(DirectedWeightedEdgeGraph<E,V> graph) Constructor from the graph for which shortest paths are to be found.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	findShortestPaths(V s) Find shortest paths to all vertices reachable from a given source vertex s.

Methods inherited from class java.lang.Object

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

Constructor Detail

BellmanFord

public BellmanFord(DirectedWeightedEdgeGraph<E,V> graph)

Constructor from the graph for which shortest paths are to be found.

Parameters:

graph - graph for which shortest paths are to be found

Method Detail

findShortestPaths

public final boolean findShortestPaths(V s)

Find shortest paths to all vertices reachable from a given source vertex s. Returns true iff there is no negative-weight cycle reachable from the source, false if there is such a cycle. In case of a negative-weight cycle, the return value of false indicates that there is no solution to the shortest path problem.

Parameters:

s - source vertex from which shortest paths are to be determined

Returns:

true iff there is no negative-weight cycle reachable from s