Package org.graph4j.shortestpath

Interface AllPairsShortestPath

All Known Implementing Classes:
BFSAllPairsShortestPath, FloydWarshallShortestPath, JohnsonShortestPath
public interface AllPairsShortestPath
A contract for all-pairs shortest path algorithms.
Author:
Cristian Frăsinaru
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    Path
    findPath(int source, int target)
    Returns the shortest path between source and target.
    Graph
    getGraph()
    Returns the input graph on which the algorithm is executed.
    static AllPairsShortestPath
    getInstance(Graph graph)
    Returns the default implementation of this interface.
    default double
    getPathWeight(int source, int target)
     
    default double[][]
    getPathWeights()
    Returns a matrix containing the weights of the shortest paths for every pair of vertices.

  • Method Details

    • getGraph

      Graph getGraph()
      Returns the input graph on which the algorithm is executed.
      Returns:
      the input graph.

    • findPath

      Path findPath(int source, int target)
      Returns the shortest path between source and target. On the first invocation of this method, it computes shortest paths between any two vertices of the graph, 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:
      source - the number of the source vertex.
      target - the number of the target vertex.
      Returns:
      the shortest path from the source to the target, or null if no path exists.

    • getPathWeight

      default double getPathWeight(int source, int target)
      Parameters:
      source - the number of the source vertex.
      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 exists.

    • getPathWeights

      default double[][] getPathWeights()
      Returns a matrix containing the weights of the shortest paths for every pair of vertices.
      Returns:
      a matrix containing the weights of the shortest paths for every pair of vertices.

    • getInstance

      static AllPairsShortestPath getInstance(Graph graph)
      Returns the default implementation of this interface.
      Parameters:
      graph - the input graph.
      Returns:
      the default implementation of this interface.