graphlab.library.algorithms.shortestpath
Class BellmanFord<VertexType extends BaseVertex,EdgeType extends BaseEdge<VertexType>>

java.lang.Object
  graphlab.library.algorithms.Algorithm
      graphlab.library.algorithms.shortestpath.BellmanFord<VertexType,EdgeType>

All Implemented Interfaces:

AlgorithmInterface, AutomatedAlgorithm

public class BellmanFord<VertexType extends BaseVertex,EdgeType extends BaseEdge<VertexType>>
extends Algorithm
implements AutomatedAlgorithm

This method finds the shortest path from a source vertex v, to all vertices of the graph. Unlike dijkstra, this method will works properly, for graphs with negative edges, as well as graphs with non negative edge's weights.

Author:

Soroush Sabet

Constructor Summary

BellmanFord()

Method Summary

java.util.Vector<VertexType>	computePaths(BaseGraph<VertexType,EdgeType> graph, VertexType Vertex) A graph with a negative cycle is not well defined as the input of a shortest path algorithm.
void	doAlgorithm()

Methods inherited from class graphlab.library.algorithms.Algorithm

acceptEventDispatcher, dispatchEvent

Methods inherited from class java.lang.Object

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

Methods inherited from interface graphlab.library.algorithms.AlgorithmInterface

acceptEventDispatcher

Constructor Detail

BellmanFord

public BellmanFord()

Method Detail

computePaths

public java.util.Vector<VertexType> computePaths(BaseGraph<VertexType,EdgeType> graph,
                                                 VertexType Vertex)

A graph with a negative cycle is not well defined as the input of a shortest path algorithm. Bellman-Ford algorithms checks for this inconvenienc, along with solving the single source shortest path algorithm.

Parameters:

graph - with arbitrary edge weights.

Vertex - as the source.

Returns:

null if there be a negative cycle in the graph; and the vector of predecessors, otherwise.

doAlgorithm

public void doAlgorithm()

Specified by:

doAlgorithm in interface AutomatedAlgorithm