Package org.graph4j.shortestpath

Class BellmanFordShortestPath

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.shortestpath.BellmanFordShortestPath
All Implemented Interfaces:
SingleSourceShortestPath
public class BellmanFordShortestPath extends GraphAlgorithm implements SingleSourceShortestPath
Bellman-Ford-Moore's algorithm finds the shortest paths between a source vertex and all the other vertices in a graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. The complexity of this implementation is O(nm), where m is the number of edges and n the number of vertices.
Author:
Cristian Frăsinaru

  • Constructor Details

    • BellmanFordShortestPath

      public BellmanFordShortestPath(Graph graph, int source)
      Creates an algorithm to find all shortest paths starting in the source.
      Parameters:
      graph - the input graph.
      source - the source vertex number.

  • Method Details

    • getSource

      public int getSource()
      Specified by:
      getSource in interface SingleSourceShortestPath
      Returns:
      the source of the paths

    • findPath

      public Path findPath(int target)
      Description copied from interface: SingleSourceShortestPath
      Returns the shortest path between source and target. On the first invocation of this method, it computes all the shortest paths starting in source and then it returns the requested one. All the shortest paths are stored for later retrieval, so subsequent invocations will return the already computed paths.
      Specified by:
      findPath in interface SingleSourceShortestPath
      Parameters:
      target - the target vertex number.
      Returns:
      the shortest path from the source to the target, or null if no path exists.

    • getPathWeight

      public double getPathWeight(int target)
      Description copied from interface: SingleSourceShortestPath
      Returns the weight of the shortest path from the source to the target. If the algorithm is designed for unweighted graphs, his method returns the number of edges in the path.
      Specified by:
      getPathWeight in interface SingleSourceShortestPath
      Parameters:
      target - the number of the target vertex
      Returns:
      the weight of the shortest path from the source to the target, or Double.POSTIVE_INFINITY if no path exist.

    • getPathWeights

      public double[] getPathWeights()
      Description copied from interface: SingleSourceShortestPath
      Returns an array containing the weights of the shortest paths from the source to all vertices. If the algorithm is designed for unweighted graphs, his method returns the number of edges in the each path.
      Specified by:
      getPathWeights in interface SingleSourceShortestPath
      Returns:
      an array containing the weights of the shortest paths from the source to all vertices.