Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class DijkstraManyToManyShortestPaths.DijkstraManyToManyShortestPathsImpl
java.lang.Object
org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>
org.jgrapht.alg.shortestpath.DijkstraManyToManyShortestPaths.DijkstraManyToManyShortestPathsImpl
- All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,
E>
- Enclosing class:
DijkstraManyToManyShortestPaths<V,
E>
private class DijkstraManyToManyShortestPaths.DijkstraManyToManyShortestPathsImpl
extends ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>
Implementation of the
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths
.
For each source vertex a single source shortest paths tree is stored. It is used to retrieve
both actual paths and theirs weights.-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
Indicates is the search spaces were computed on the edge reversed graph.private final Map
<V, ShortestPathAlgorithm.SingleSourcePaths<V, E>> Map from source vertices to corresponding single source shortest path trees. -
Constructor Summary
ConstructorsConstructorDescriptionDijkstraManyToManyShortestPathsImpl
(Set<V> sources, Set<V> targets, boolean reversed, Map<V, ShortestPathAlgorithm.SingleSourcePaths<V, E>> searchSpaces) Constructs an instance of the algorithm for the givensources
,targets
,reversed
andsearchSpaces
. -
Method Summary
Modifier and TypeMethodDescriptionReturn the path from thesource
vertex to thetarget
vertex.double
Return the weight of the path from thesource
vertex to thetarget
vertex orDouble.POSITIVE_INFINITY
if there is no such path in the graph.Methods inherited from class org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl
assertCorrectSourceAndTarget, getSources, getTargets
-
Field Details
-
reversed
private boolean reversedIndicates is the search spaces were computed on the edge reversed graph. -
searchSpaces
Map from source vertices to corresponding single source shortest path trees.
-
-
Constructor Details
-
DijkstraManyToManyShortestPathsImpl
DijkstraManyToManyShortestPathsImpl(Set<V> sources, Set<V> targets, boolean reversed, Map<V, ShortestPathAlgorithm.SingleSourcePaths<V, E>> searchSpaces) Constructs an instance of the algorithm for the givensources
,targets
,reversed
andsearchSpaces
.- Parameters:
sources
- source verticestargets
- target verticesreversed
- if search spaces are reversedsearchSpaces
- single source shortest paths trees map
-
-
Method Details
-
getPath
Return the path from thesource
vertex to thetarget
vertex. If no such path exists, null is returned.- Parameters:
source
- source vertextarget
- target vertex- Returns:
- path between
source
andtarget
or null if no such path exists
-
getWeight
Return the weight of the path from thesource
vertex to thetarget
vertex orDouble.POSITIVE_INFINITY
if there is no such path in the graph. The weight of the path between a vertex and itself is always zero.- Parameters:
source
- source vertextarget
- target vertex- Returns:
- the weight of the path between source and sink vertices or
Double.POSITIVE_INFINITY
in case no such path exists
-