Package org.graph4j.shortestpath

Interface SingleSourceShortestPath

All Known Implementing Classes:
BellmanFordShortestPath, BFSSingleSourceShortestPath, DijkstraShortestPathBase, DijkstraShortestPathDefault, DijkstraShortestPathHeap
public interface SingleSourceShortestPath
Contract for single-source shortest path algorithms. The graph and the source will be specified by the implementation constructors.
Author:
Cristian Frăsinaru

  • Method Summary

    Modifier and Type
    Method
    Description
    default Path
    computePath(int target)
    Attempts at finding the shortest path from the source to the target without computing all the paths.
    Path
    findPath(int target)
    Returns the shortest path between source and target.
    Graph
    getGraph()
     
    static SingleSourceShortestPath
    getInstance(Graph graph, int source)
    Returns the default implementation of this interface.
    default double
    getPathWeight(int target)
    Returns the weight of the shortest path from the source to the target.
    default double[]
    getPathWeights()
    Returns an array containing the weights of the shortest paths from the source to all vertices.
    int
    getSource()
     

  • Method Details

    • getGraph

      Graph getGraph()
      Returns:
      the input graph.

    • getSource

      int getSource()
      Returns:
      the source of the paths

    • computePath

      default Path computePath(int target)
      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.
      Parameters:
      target - the target vertex number.
      Returns:
      the shortest path from the source to the target.

    • findPath

      Path findPath(int target)
      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.
      Parameters:
      target - the target vertex number.
      Returns:
      the shortest path from the source to the target, or null if no path exists.

    • getPathWeight

      default double getPathWeight(int target)
      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.
      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

      default double[] getPathWeights()
      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.
      Returns:
      an array containing the weights of the shortest paths from the source to all vertices.

    • getInstance

      static SingleSourceShortestPath getInstance(Graph graph, int source)
      Returns the default implementation of this interface.
      Parameters:
      graph - the input graph.
      source - the source vertex.
      Returns:
      the default implementation of this interface.