V
- the graph vertex typeE
- the graph edge typepublic class BellmanFordShortestPath<V,E> extends Object
ShortestPathAlgorithm.SingleSourcePaths<V,E>
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 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.
|
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.
|
protected V startVertex
protected int nMaxHops
protected double epsilon
protected final Graph<V,E> graph
public BellmanFordShortestPath(Graph<V,E> graph)
graph
- the input graphpublic BellmanFordShortestPath(Graph<V,E> graph, int nMaxHops)
graph
- the input graphnMaxHops
- maximum number of edges of the calculated pathspublic BellmanFordShortestPath(Graph<V,E> graph, int nMaxHops, double epsilon)
graph
- the input graphnMaxHops
- maximum number of edges of the calculated paths.epsilon
- tolerance factor when comparing floating point valuespublic GraphPath<V,E> getPath(V source, V sink)
source
- the source vertexsink
- the target vertexpublic ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
getPaths
in interface ShortestPathAlgorithm<V,E>
source
- the source vertexpublic static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph, V source, V sink)
V
- the graph vertex typeE
- the graph edge typegraph
- the graph to be searchedsource
- the vertex at which the path should startsink
- the vertex at which the path should endpublic double getPathWeight(V source, V sink)
Double.POSITIVE_INFINITY
if no path exists.getPathWeight
in interface ShortestPathAlgorithm<V,E>
source
- the source vertexsink
- the sink vertexDouble.POSITIVE_INFINITY
if no path existsprotected final GraphPath<V,E> createEmptyPath(V source, V sink)
source
- the source vertexsink
- the sink vertexCopyright © 2017. All rights reserved.