Class DijkstraManyToManyShortestPaths<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,
,E> ShortestPathAlgorithm<V,
E>
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.
 Author:
 Semen Chudakov
 See Also:

Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm
ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,
E>, ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> 
Field Summary

Constructor Summary
ConstructorDescriptionDijkstraManyToManyShortestPaths
(Graph<V, E> graph) Constructs an instance of the algorithm for a givengraph
. 
Method Summary
Modifier and TypeMethodDescriptiongetManyToManyPaths
(Set<V> sources, Set<V> targets) Computes shortest paths from all vertices insources
to all vertices intargets
.Get a shortest path from a source vertex to a sink vertex.Compute all shortest paths starting from a single source vertex.double
getPathWeight
(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.protected static <V,
E> ShortestPathAlgorithm.SingleSourcePaths<V, E> getShortestPathsTree
(Graph<V, E> graph, V source, Set<V> targets) Computes shortest paths tree starting atsource
and stopping as soon as all of thetargets
are reached.

Field Details

graph


Constructor Details

DijkstraManyToManyShortestPaths
Constructs an instance of the algorithm for a givengraph
. 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 insources
to all vertices intargets
. Parameters:
sources
 list of sources verticestargets
 list of target vertices Returns:
 computed shortest paths

getPath
Get a shortest path from a source vertex to a sink vertex. Specified by:
getPath
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertexsink
 the target vertex Returns:
 a shortest path or null if no path exists

getPathWeight
Get the weight of the shortest path from a source vertex to a sink vertex. ReturnsDouble.POSITIVE_INFINITY
if no path exists. Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertexsink
 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
Compute all shortest paths starting from a single source vertex. Specified by:
getPaths
in interfaceShortestPathAlgorithm<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 atsource
and stopping as soon as all of thetargets
are reached. Here theDijkstraClosestFirstIterator
is used. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 a graphsource
 source vertextargets
 target vertices Returns:
 shortest paths starting from
source
and reaching alltargets
