Package org.graph4j.shortestpath

Class BFSSingleSourceShortestPath

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.shortestpath.BFSSingleSourceShortestPath
All Implemented Interfaces:
SingleSourceShortestPath
public class BFSSingleSourceShortestPath extends GraphAlgorithm implements SingleSourceShortestPath
Determines the shortest paths from a source vertex to all other vertices, in an unweighted graph, using a breadth-first traversal.
Author:
Cristian Frăsinaru

  • Field Details

    • source

      protected final int source

    • dist

      protected double[] dist

    • before

      protected int[] before

  • Constructor Details

    • BFSSingleSourceShortestPath

      public BFSSingleSourceShortestPath(Graph graph, int source)
      Creates an algorithm to find all shortest paths starting in the specified source, in an unweighted graph. If the input graph has weights on its edges, they are ignored.
      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

    • computePath

      public Path computePath(int target)
      Description copied from interface: SingleSourceShortestPath
      Attempts at finding the shortest path from the source to the target without computing all the paths. It may be implemented by starting the computation for all the shortest paths and stopping the algorithm when the shortest path to the target is found. If a implementation does not have this ability, it simply invokes getPath instead.
      Specified by:
      computePath in interface SingleSourceShortestPath
      Parameters:
      target - the target vertex number.
      Returns:
      the shortest path from the source to the target.

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

    • compute

      protected void compute(int target)

    • createPathEndingIn

      protected Path createPathEndingIn(int vi)