org.jgrapht.alg

Class BellmanFordShortestPath<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type

```public class BellmanFordShortestPath<V,E>
extends Object```
Bellman-Ford algorithm: weights could be negative, paths could be constrained by a maximum number of edges.
• Field Summary

Fields
Modifier and Type Field and Description
`protected Graph<V,E>` `graph`
Graph on which shortest paths are searched.
`protected V` `startVertex`
Start vertex.
• Constructor Summary

Constructors
Constructor and Description
```BellmanFordShortestPath(Graph<V,E> graph, V startVertex)```
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.
```BellmanFordShortestPath(Graph<V,E> graph, V startVertex, int nMaxHops)```
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.
```BellmanFordShortestPath(Graph<V,E> graph, V startVertex, int nMaxHops, double epsilon)```
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.
• Method Summary

All Methods
Modifier and Type Method and Description
`static <V,E> List<E>` ```findPathBetween(Graph<V,E> graph, V startVertex, V endVertex)```
Convenience method to find the shortest path via a single static method call.
`double` `getCost(V endVertex)`
Get the cost of the shortest path to a vertex.
`List<E>` `getPathEdgeList(V endVertex)`
Get the shortest path to a vertex.
• Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Field Detail

• graph

`protected Graph<V,E> graph`
Graph on which shortest paths are searched.
• startVertex

`protected V startVertex`
Start vertex.
• Constructor Detail

• BellmanFordShortestPath

```public BellmanFordShortestPath(Graph<V,E> graph,
V startVertex)```
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.
Parameters:
`graph` - the graph
`startVertex` - the start vertex
• BellmanFordShortestPath

```public BellmanFordShortestPath(Graph<V,E> graph,
V startVertex,
int nMaxHops)```
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.
Parameters:
`graph` - the graph
`startVertex` - the start vertex
`nMaxHops` - maximum number of edges of the calculated paths
• BellmanFordShortestPath

```public BellmanFordShortestPath(Graph<V,E> graph,
V startVertex,
int nMaxHops,
double epsilon)```
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.
Parameters:
`graph` - the graph
`startVertex` - the start vertex
`nMaxHops` - maximum number of edges of the calculated paths.
`epsilon` - tolerance factor when comparing floating point values
• Method Detail

• getCost

`public double getCost(V endVertex)`
Get the cost of the shortest path to a vertex.
Parameters:
`endVertex` - the end vertex
Returns:
the cost of the shortest path between the start vertex and the end vertex.
• getPathEdgeList

`public List<E> getPathEdgeList(V endVertex)`
Get the shortest path to a vertex.
Parameters:
`endVertex` - the end vertex
Returns:
list of edges, or null if no path exists between the start vertex and the end vertex
• findPathBetween

```public static <V,E> List<E> findPathBetween(Graph<V,E> graph,
V startVertex,
V endVertex)```
Convenience method to find the shortest path via a single static method call. If you need a more advanced search (e.g. limited by hops, or computation of the path length), use the constructor instead.
Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
Parameters:
`graph` - the graph to be searched
`startVertex` - the vertex at which the path should start
`endVertex` - the vertex at which the path should end
Returns:
List of Edges, or null if no path exists