Package org.graph4j.shortestpath

Class DijkstraShortestPathBase

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.shortestpath.DijkstraShortestPathBase
All Implemented Interfaces:
SingleSourceShortestPath
Direct Known Subclasses:
DijkstraShortestPathDefault, DijkstraShortestPathHeap
public abstract class DijkstraShortestPathBase extends GraphAlgorithm implements SingleSourceShortestPath
Dijkstra's algorithm finds the minimum cost paths between a vertex (called source) and all the other vertices in a graph, with the condition that there are no negative weighted edges. The cost of a path is the sum of its edges weights. If the graph contains a negative weighted edge, an exception will be thrown.
Author:
Cristian Frăsinaru
See Also:

  • Field Details

    • source

      protected final int source

    • vertices

      protected final int[] vertices

    • cost

      protected double[] cost

    • before

      protected int[] before

    • size

      protected int[] size

    • solved

      protected boolean[] solved

    • numSolved

      protected int numSolved

  • Constructor Details

    • DijkstraShortestPathBase

      public DijkstraShortestPathBase(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

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

    • preCompute

      protected void preCompute()

    • postUpdate

      protected void postUpdate(int vi)

    • findMinIndex

      protected abstract int findMinIndex()

    • compute

      protected void compute(int target)

    • createPathEndingIn

      protected Path createPathEndingIn(int vi)