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

Class DefaultManyToManyShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.DefaultManyToManyShortestPaths<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,E>, ShortestPathAlgorithm<V,E>
public class DefaultManyToManyShortestPaths<V,E> extends Object
Naive algorithm for many-to-many shortest paths problem using.

Time complexity of the algorithm is $O(|S||T|C)$, where $S$ is the set of source vertices, $T$ is the set of target vertices and $C$ is the complexity of the ShortestPathAlgorithm.getPath(Object, Object) method of the provided implementation.

For every pair of source and target vertices computes a shortest path between them using provided implementation of ShortestPathAlgorithm. By default this implementation uses BidirectionalDijkstraShortestPath. If desired, a different implementation can be provided via the function constructor parameter.

The computation complexity of the algorithm consists of two main components - the $|S||T|$ multiplier and the $C$ multiplier. This yields two bottlenecks for the algorithm. First of them is the situation when the total number calls to ShortestPathAlgorithm.getPath(Object, Object) is large. The second situation is when the complexity of the individual call to ShortestPathAlgorithm.getPath(Object, Object) takes a lot of time. Therefore the ideal use cases for this algorithm are small graphs or large graphs with low total number of source and target vertices.

Author:
Semen Chudakov
See Also:

  • Field Details

    • graph

      protected final Graph<V,E> graph

  • Constructor Details

    • DefaultManyToManyShortestPaths

      public DefaultManyToManyShortestPaths(Graph<V,E> graph)
      Constructs a new instance of the algorithm for a given graph. The function is defaulted to returning BidirectionalDijkstraShortestPath.
      Parameters:
      graph - a graph

    • DefaultManyToManyShortestPaths

      public DefaultManyToManyShortestPaths(Graph<V,E> graph, Function<Graph<V,E>,ShortestPathAlgorithm<V,E>> function)
      Constructs a new instance of the algorithm for a given graph and function.
      Parameters:
      graph - a graph
      function - provides implementation of ShortestPathAlgorithm

  • Method Details

    • getManyToManyPaths

      public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(Set<V> sources, Set<V> targets)
      Description copied from interface: ManyToManyShortestPathsAlgorithm
      Computes shortest paths from all vertices in sources to all vertices in targets.
      Parameters:
      sources - list of sources vertices
      targets - list of target vertices
      Returns:
      computed shortest paths

    • getPath

      public GraphPath<V,E> getPath(V source, V sink)
      Get a shortest path from a source vertex to a sink vertex.
      Specified by:
      getPath in interface ShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      sink - the target vertex
      Returns:
      a shortest path or null if no path exists

    • 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

    • 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>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths

    • getShortestPathsTree

      protected static <V, E> ShortestPathAlgorithm.SingleSourcePaths<V,E> getShortestPathsTree(Graph<V,E> graph, V source, Set<V> targets)
      Computes shortest paths tree starting at source and stopping as soon as all of the targets are reached. Here the DijkstraClosestFirstIterator is used.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - a graph
      source - source vertex
      targets - target vertices
      Returns:
      shortest paths starting from source and reaching all targets