Class DijkstraManyToManyShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths<V,E>
org.jgrapht.alg.shortestpath.DijkstraManyToManyShortestPaths<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 DijkstraManyToManyShortestPaths<V,E> extends BaseManyToManyShortestPaths<V,E>
Naive algorithm for many-to-many shortest paths problem using DijkstraClosestFirstIterator.

Complexity of the algorithm is $O(min(|S|,|T|)*(V\log V + E))$, where $S$ is the set of source vertices, $T$ is the set of target vertices, $V$ is the set of graph vertices and $E$ is the set of graph edges of the graph.

For each source vertex a single source shortest paths search is performed, which is stopped as soon as all target vertices are reached. Shortest paths trees are constructed using DijkstraClosestFirstIterator. In case $|T| > |S|$ the searches are performed on the reversed graph using $|T|$ as source vertices and $|S|$ as target vertices. This allows to reduce the total number of searches from $|S|$ to $min(|S|,|T|)$.

The main bottleneck of this algorithm is the memory usage to store individual shortest paths trees for every source vertex, as they may take a lot of space. Considering this, the typical use case of this algorithm are small graphs or large graphs with small total number of source and target vertices.

See Also:
  • Constructor Details

    • DijkstraManyToManyShortestPaths

      public DijkstraManyToManyShortestPaths(Graph<V,E> graph)
      Constructs an instance of the algorithm for a given graph.
      Parameters:
      graph - underlying graph
  • Method Details

    • getManyToManyPaths

      public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(Set<V> sources, Set<V> targets)
      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