Class BellmanFordShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.BellmanFordShortestPath<V,E>

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
    Description
    protected Graph<V,E>
    Graph on which shortest paths are searched.
    protected V
    Start vertex.
  • 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

    Modifier and Type
    Method
    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)
     
    getPathEdgeList(V endVertex)
     

    Methods inherited from class java.lang.Object

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

    • graph

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

      protected V startVertex
      Start vertex.
  • Constructor Details

    • 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 Details

    • 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 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> 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