Package org.jgrapht.alg
Class BellmanFordShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.BellmanFordShortestPath<V,E>
-
public class BellmanFordShortestPath<V,E> extends java.lang.Object
Bellman-Ford algorithm: weights could be negative, paths could be constrained by a maximum number of edges.
-
-
Constructor Summary
Constructors Constructor 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 Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static <V,E>
java.util.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)
java.util.List<E>
getPathEdgeList(V endVertex)
-
-
-
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
-startVertex
-
-
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
-startVertex
-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
-startVertex
-nMaxHops
- maximum number of edges of the calculated paths.epsilon
- tolerance factor.
-
-
Method Detail
-
getCost
public double getCost(V endVertex)
- Parameters:
endVertex
- end vertex.- Returns:
- the cost of the shortest path between the start vertex and the end vertex.
-
getPathEdgeList
public java.util.List<E> getPathEdgeList(V endVertex)
- Parameters:
endVertex
- end vertex.- Returns:
- list of
Edge
, or null if no path exists between the start vertex and the end vertex.
-
findPathBetween
public static <V,E> java.util.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.- Parameters:
graph
- the graph to be searchedstartVertex
- the vertex at which the path should startendVertex
- the vertex at which the path should end- Returns:
- List of Edges, or null if no path exists
-
-