Class BellmanFordShortestPath<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    ShortestPathAlgorithm<V,​E>

    public class BellmanFordShortestPath<V,​E>
    extends BaseShortestPathAlgorithm<V,​E>
    The Bellman-Ford algorithm. Computes shortest paths form a single source vertex to all the other vertices in a weighted graph. Supports graphs with negative weights. Additionally the user can constrain the paths by a maximum number of edges. The algorithm has worst-case complexity O(nm) when n is the number of vertices and m the number of edges of the input graph.
    • Field Detail

      • startVertex

        protected V startVertex
        Start vertex.
      • nMaxHops

        protected int nMaxHops
        Maximum number of edges of the calculated paths.
      • epsilon

        protected double epsilon
        Tolerance when comparing floating point values.
    • Constructor Detail

      • BellmanFordShortestPath

        public BellmanFordShortestPath​(Graph<V,​E> graph)
        Construct a new instance of the Bellman-Ford algorithm.
        Parameters:
        graph - the input graph
      • BellmanFordShortestPath

        public BellmanFordShortestPath​(Graph<V,​E> graph,
                                       int nMaxHops)
        Construct a new instance of the Bellman-Ford algorithm.
        Parameters:
        graph - the input graph
        nMaxHops - maximum number of edges of the calculated paths
      • BellmanFordShortestPath

        public BellmanFordShortestPath​(Graph<V,​E> graph,
                                       int nMaxHops,
                                       double epsilon)
        Construct a new instance of the Bellman-Ford algorithm.
        Parameters:
        graph - the input graph
        nMaxHops - maximum number of edges of the calculated paths.
        epsilon - tolerance factor when comparing floating point values
    • Method Detail

      • getPath

        public GraphPath<V,​E> getPath​(V source,
                                            V sink)
        Get a shortest path from a source vertex to a sink vertex.
        Parameters:
        source - the source vertex
        sink - the target vertex
        Returns:
        a shortest path or null if no path exists
      • findPathBetween

        public static <V,​E> GraphPath<V,​E> findPathBetween​(Graph<V,​E> graph,
                                                                       V source,
                                                                       V sink)
        Find a path between two vertices. For a more advanced search (e.g. limited by radius), use the constructor instead.
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        graph - the graph to be searched
        source - the vertex at which the path should start
        sink - the vertex at which the path should end
        Returns:
        a shortest path, or null if no path exists