Package org.jgrapht.alg
Class BellmanFordShortestPath<V,E>
java.lang.Object
org.jgrapht.alg.BellmanFordShortestPath<V,E>
Bellman-Ford
algorithm: weights could be negative, paths could be constrained by a
maximum number of edges.
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionBellmanFordShortestPath
(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
Modifier and TypeMethodDescriptionstatic <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
getPathEdgeList
(V endVertex)
-
Field Details
-
graph
Graph on which shortest paths are searched. -
startVertex
Start vertex.
-
-
Constructor Details
-
BellmanFordShortestPath
Creates an object to calculate shortest paths between the start vertex and others vertices using the Bellman-Ford algorithm.- Parameters:
graph
-startVertex
-
-
BellmanFordShortestPath
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
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 Details
-
getCost
- Parameters:
endVertex
- end vertex.- Returns:
- the cost of the shortest path between the start vertex and the end vertex.
-
getPathEdgeList
- Parameters:
endVertex
- end vertex.- Returns:
- list of
Edge
, or null if no path exists between the start vertex and the end vertex.
-
findPathBetween
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
-