org.jgrapht.alg
Class BellmanFordShortestPath<V,E>

java.lang.Object
  extended by 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.


Field Summary
protected  Graph<V,E> graph
          Graph on which shortest paths are searched.
protected  V startVertex
          Start vertex.
 
Constructor Summary
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
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)
           
 
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 -
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 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