Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class DijkstraManyToManyShortestPaths<V,E>

java.lang.Object

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 Object

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.

Author:

Semen Chudakov

See Also:

DefaultManyToManyShortestPaths, CHManyToManyShortestPaths

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

Fields

Modifier and Type	Field	Description
protected Graph<V,E>	graph

Constructor Summary

Constructors

Constructor	Description
DijkstraManyToManyShortestPaths(Graph<V,E> graph)	Constructs an instance of the algorithm for a given graph.

Method Summary

Modifier and Type	Method	Description
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>	getManyToManyPaths(Set<V> sources, Set<V> targets)	Computes shortest paths from all vertices in sources to all vertices in targets.
GraphPath<V,E>	getPath(V source, V sink)	Get a shortest path from a source vertex to a sink vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,E>	getPaths(V source)	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 at source and stopping as soon as all of the targets are reached.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graph

protected final Graph<V,E> graph

Constructor Detail

DijkstraManyToManyShortestPaths

public DijkstraManyToManyShortestPaths(Graph<V,E> graph)

Constructs an instance of the algorithm for a given graph.

Parameters:

graph - underlying graph

Method Detail

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

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