Package org.jgrapht.alg.shortestpath
Class BellmanFordShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
-
- org.jgrapht.alg.shortestpath.BellmanFordShortestPath<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
public class BellmanFordShortestPath<V,E> extends BaseShortestPathAlgorithm<V,E>
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 Modifier and Type Class Description private class
BellmanFordShortestPath.PathElementSingleSourcePaths
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private static double
DEFAULT_EPSILON
protected double
epsilon
Tolerance when comparing floating point values.protected int
nMaxHops
Maximum number of edges of the calculated paths.protected V
startVertex
Start vertex.-
Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
graph
-
-
Constructor Summary
Constructors Constructor 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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPathWeight
-
-
-
-
Field Detail
-
DEFAULT_EPSILON
private static final double DEFAULT_EPSILON
- See Also:
- Constant Field Values
-
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.
-
-
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 graphnMaxHops
- 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 graphnMaxHops
- 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 vertexsink
- 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 interfaceShortestPathAlgorithm<V,E>
- Overrides:
getPaths
in classBaseShortestPathAlgorithm<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 typeE
- the graph edge type- Parameters:
graph
- the graph to be searchedsource
- the vertex at which the path should startsink
- the vertex at which the path should end- Returns:
- a shortest path, or null if no path exists
-
-