com.hp.ds.graph

Class BellmanFordGraphSearch

java.lang.Object

com.hp.ds.graph.AbstractGraphPathSearch

com.hp.ds.graph.BellmanFordGraphSearch

All Implemented Interfaces:

GraphPathSearch

public class BellmanFordGraphSearch
extends AbstractGraphPathSearch

Implementation of the Bellman-Ford shortest-path graph search algorithm for directed graphs with negative cycles.

Author:

Thomas Vachuska

Nested Class Summary

Nested classes/interfaces inherited from class com.hp.ds.graph.AbstractGraphPathSearch

AbstractGraphPathSearch.DefaultResult

Nested classes/interfaces inherited from interface com.hp.ds.graph.GraphPathSearch

GraphPathSearch.Result

Field Summary

Fields inherited from class com.hp.ds.graph.AbstractGraphPathSearch

E_GRAPH_NULL, E_NOT_IN_GRAPH, E_SRC_NULL

Constructor Summary

Constructors

Constructor and Description
BellmanFordGraphSearch()

Method Summary

Methods

Modifier and Type	Method and Description
GraphPathSearch.Result	search(Graph g, Vertex src, Vertex dst, EdgeWeight ew) Search the graph producing a set of paths.

Methods inherited from class com.hp.ds.graph.AbstractGraphPathSearch

buildPaths, validate

Methods inherited from class java.lang.Object

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

Constructor Detail

BellmanFordGraphSearch

public BellmanFordGraphSearch()

Method Detail

search

public GraphPathSearch.Result search(Graph g,
                            Vertex src,
                            Vertex dst,
                            EdgeWeight ew)

Description copied from interface: GraphPathSearch

Search the graph producing a set of paths.

Parameters:

g - graph to be searched

src - source node; implementations may leave this as optional

dst - destination node; implementations may leave this as optional

ew - optional edge weight function

Returns:

search result