org.jgrapht.alg.shortestpath

Class BellmanFordShortestPath<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.BellmanFordShortestPath<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

ShortestPathAlgorithm<V,E>

public class BellmanFordShortestPath<V,E>
extends Object

The Bellman-Ford algorithm. Computes shortest paths form a single source vertex to all the other vertices in a weighted graph. Supports graphs with negative weights. Additionally the user can constrain the paths by a maximum number of edges. The algorithm has worst-case complexity O(nm) when n is the number of vertices and m the number of edges of the input graph.

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,E>

Field Summary

Fields

Modifier and Type	Field and Description
protected double	epsilon Tolerance when comparing floating point values.
protected Graph<V,E>	graph
protected int	nMaxHops Maximum number of edges of the calculated paths.
protected V	startVertex Start vertex.

Constructor Summary

Constructors

Constructor and Description
BellmanFordShortestPath(Graph<V,E> graph) Construct a new instance of the Bellman-Ford algorithm.
BellmanFordShortestPath(Graph<V,E> graph, int nMaxHops) Construct a new instance of the Bellman-Ford algorithm.
BellmanFordShortestPath(Graph<V,E> graph, int nMaxHops, double epsilon) Construct a new instance of the Bellman-Ford algorithm.

Method Summary

Modifier and Type	Method and Description
protected GraphPath<V,E>	createEmptyPath(V source, V sink) Create an empty path.
static <V,E> GraphPath<V,E>	findPathBetween(Graph<V,E> graph, V source, V sink) Find a path between two vertices.
GraphPath<V,E>	getPath(V source, V sink) Get a shortest path from a source vertex to a sink vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,E>	getPaths(V source) Compute all shortest paths starting from a single source vertex.
double	getPathWeight(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.

Methods inherited from class java.lang.Object

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

Field Detail

startVertex

protected V startVertex

Start vertex.

nMaxHops

protected int nMaxHops

Maximum number of edges of the calculated paths.

epsilon

protected double epsilon

Tolerance when comparing floating point values.

graph

protected final Graph<V,E> graph

Constructor Detail

BellmanFordShortestPath

public BellmanFordShortestPath(Graph<V,E> graph)

Construct a new instance of the Bellman-Ford algorithm.

Parameters:

graph - the input graph

BellmanFordShortestPath

public BellmanFordShortestPath(Graph<V,E> graph,
                               int nMaxHops)

Construct a new instance of the Bellman-Ford algorithm.

Parameters:

graph - the input graph

nMaxHops - maximum number of edges of the calculated paths

BellmanFordShortestPath

public BellmanFordShortestPath(Graph<V,E> graph,
                               int nMaxHops,
                               double epsilon)

Construct a new instance of the Bellman-Ford algorithm.

Parameters:

graph - the input graph

nMaxHops - maximum number of edges of the calculated paths.

epsilon - tolerance factor when comparing floating point values

Method Detail

getPath

public GraphPath<V,E> getPath(V source,
                              V sink)

Get a shortest path from a source vertex to a sink vertex.

Parameters:

source - the source vertex

sink - the target vertex

Returns:

a shortest path or null if no path exists

getPaths

public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)

Compute all shortest paths starting from a single source vertex.

Specified by:

getPaths in interface ShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

Returns:

the shortest paths

findPathBetween

public static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph,
                                                   V source,
                                                   V sink)

Find a path between two vertices. For a more advanced search (e.g. limited by radius), use the constructor instead.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

graph - the graph to be searched

source - the vertex at which the path should start

sink - the vertex at which the path should end

Returns:

a shortest path, or null if no path exists

getPathWeight

public double getPathWeight(V source,
                            V sink)

Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.

Specified by:

getPathWeight in interface ShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

sink - the sink vertex

Returns:

the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists

createEmptyPath

protected final GraphPath<V,E> createEmptyPath(V source,
                                               V sink)

Create an empty path. Returns null if the source vertex is different than the target vertex.

Parameters:

source - the source vertex

sink - the sink vertex

Returns:

an empty path or null null if the source vertex is different than the target vertex