java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
- Direct Known Subclasses:
AStarShortestPath
,BaseBidirectionalShortestPathAlgorithm
,BellmanFordShortestPath
,BFSShortestPath
,ContractionHierarchyBidirectionalDijkstra
,DeltaSteppingShortestPath
,DijkstraShortestPath
,FloydWarshallShortestPaths
,IntVertexDijkstraShortestPath
,JohnsonShortestPaths
,TransitNodeRoutingShortestPath
A base implementation of the shortest path interface.
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
FieldsModifier and TypeFieldDescriptionThe underlying graph.protected static final String
Error message for reporting the existence of a negative-weight cycle.protected static final String
Error message for reporting that a sink vertex is missing.protected static final String
Error message for reporting that a source vertex is missing. -
Constructor Summary
ConstructorsConstructorDescriptionBaseShortestPathAlgorithm
(Graph<V, E> graph) Constructs a new instance of the algorithm for a given graph. -
Method Summary
Modifier and TypeMethodDescriptioncreateEmptyPath
(V source, V sink) Create an empty path.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.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
getPath
-
Field Details
-
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.- See Also:
-
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.- See Also:
-
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.- See Also:
-
graph
The underlying graph.
-
-
Constructor Details
-
BaseShortestPathAlgorithm
Constructs a new instance of the algorithm for a given graph.- Parameters:
graph
- the graph
-
-
Method Details
-
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
-
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
-
createEmptyPath
Create an empty path. Returns null if the source vertex is different than the target vertex.- Parameters:
source
- the source vertexsink
- the sink vertex- Returns:
- an empty path or null null if the source vertex is different than the target vertex
-