Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class DijkstraShortestPath<V,​E>

java.lang.Object
org.jgrapht.alg.shortestpath.DijkstraShortestPath<V,​E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ShortestPathAlgorithm<V,​E>
public final class DijkstraShortestPath<V,​E>
extends java.lang.Object
An implementation of Dijkstra's shortest path algorithm using a pairing heap by default. A custom heap implementation can by specified during the construction time.
Author:
John V. Sichi

  • Field Details

  • Constructor Details

    • DijkstraShortestPath

      public DijkstraShortestPath​(Graph<V,​E> graph)
      Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation.
      Parameters:
      graph - the graph

    • DijkstraShortestPath

      public DijkstraShortestPath​(Graph<V,​E> graph, double radius)
      Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation.
      Parameters:
      graph - the graph
      radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search

    • DijkstraShortestPath

      public DijkstraShortestPath​(Graph<V,​E> graph, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,​Pair<V,​E>>> heapSupplier)
      Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use the heap supplied by the heapSupplier
      Parameters:
      graph - the graph
      heapSupplier - supplier of the preferable heap implementation

    • DijkstraShortestPath

      public DijkstraShortestPath​(Graph<V,​E> graph, double radius, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,​Pair<V,​E>>> heapSupplier)
      Constructs a new instance of the algorithm for a given graph.
      Parameters:
      graph - the graph
      radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search
      heapSupplier - supplier of the preferable heap implementation

  • Method Details

    • findPathBetween

      public static <V,​ E> GraphPath<V,​E> findPathBetween​(Graph<V,​E> graph, V source, V sink)
      Find a path between two vertices. For a more advanced search (e.g. limited by radius or using another heap), use the constructor instead.
      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

    • 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

    • getPaths

      public ShortestPathAlgorithm.SingleSourcePaths<V,​E> getPaths​(V source)
      Compute all shortest paths starting from a single source vertex.

      Note that in the case of Dijkstra's algorithm it is more efficient to compute all single-source shortest paths using this method than repeatedly invoking getPath(Object, Object) for the same source but different sink vertex.

      Specified by:
      getPaths in interface ShortestPathAlgorithm<V,​E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths

    • getPathWeight

      public double getPathWeight​(V source, V sink)
      Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
      Specified by:
      getPathWeight in interface ShortestPathAlgorithm<V,​E>
      Parameters:
      source - the source vertex
      sink - the sink vertex
      Returns:
      the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists

    • createEmptyPath

      protected final GraphPath<V,​E> createEmptyPath​(V source, V sink)
      Create an empty path. Returns null if the source vertex is different than the target vertex.
      Parameters:
      source - the source vertex
      sink - the sink vertex
      Returns:
      an empty path or null null if the source vertex is different than the target vertex