Class DefaultManyToManyShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths<V,E>
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 BaseManyToManyShortestPaths<V,E>
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.

See Also: