Class BFSShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.BFSShortestPath<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ShortestPathAlgorithm<V,E>

public class BFSShortestPath<V,E> extends BaseShortestPathAlgorithm<V,E>
The BFS Shortest Path algorithm.

An implementation of BFS shortest path algorithm to compute shortest paths from a single source vertex to all other vertices in an unweighted graph.

The running time is $O(|V|+|E|)$.

  • Constructor Details

    • BFSShortestPath

      public BFSShortestPath(Graph<V,E> graph)
      Construct a new instance.
      Parameters:
      graph - the input graph
  • Method Details

    • getPaths

      public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
      Compute all shortest paths starting from a single source vertex.
      Specified by:
      getPaths in interface ShortestPathAlgorithm<V,E>
      Overrides:
      getPaths in class BaseShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths
    • 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.
      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