Class 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

      Fields 
      Modifier and Type Field Description
      protected Graph<V,​E> graph
      Graph on which shortest paths are searched.
      protected V startVertex
      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

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