Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Shortest-path related algorithms.

Interface Summary

Interface	Description
PathValidator<V,E>	May be used to provide external path validations in addition to the basic validations done by KShortestSimplePaths - that the path is from source to target and that it does not contain loops.

Class Summary

Class	Description
AllDirectedPaths<V,E>	A Dijkstra-like algorithm to find all paths between two sets of nodes in a directed graph, with options to search only simple paths and to limit the path length.
ALTAdmissibleHeuristic<V,E>	An admissible heuristic for the A* algorithm using a set of landmarks and the triangle inequality.
AStarShortestPath<V,E>	A* shortest path.
BaseBidirectionalShortestPathAlgorithm<V,E>	Base class for the bidirectional shortest path algorithms.
BellmanFordShortestPath<V,E>	The Bellman-Ford algorithm.
BFSShortestPath<V,E>	The BFS Shortest Path algorithm.
BhandariKDisjointShortestPaths<V,E>	An implementation of Bhandari algorithm for finding $K$ edge-disjoint shortest paths.
BidirectionalAStarShortestPath<V,E>	A bidirectional version of A* algorithm.
BidirectionalDijkstraShortestPath<V,E>	A bidirectional version of Dijkstra's algorithm.
CHManyToManyShortestPaths<V,E>	Efficient algorithm for the many-to-many shortest paths problem based on contraction hierarchy.
ContractionHierarchyBidirectionalDijkstra<V,E>	Implementation of the hierarchical query algorithm based on the bidirectional Dijkstra search.
ContractionHierarchyPrecomputation<V,E>	Parallel implementation of the contraction hierarchy route planning precomputation technique.
ContractionHierarchyPrecomputation.ContractionEdge<E1>	Edge for building the contraction hierarchy.
ContractionHierarchyPrecomputation.ContractionHierarchy<V,E>	Return type of this algorithm.
ContractionHierarchyPrecomputation.ContractionVertex<V1>	Vertex for building the contraction hierarchy, which contains an original vertex from graph.
DefaultManyToManyShortestPaths<V,E>	Naive algorithm for many-to-many shortest paths problem using.
DeltaSteppingShortestPath<V,E>	Parallel implementation of a single-source shortest path algorithm: the delta-stepping algorithm.
DijkstraManyToManyShortestPaths<V,E>	Naive algorithm for many-to-many shortest paths problem using DijkstraClosestFirstIterator.
DijkstraShortestPath<V,E>	An implementation of Dijkstra's shortest path algorithm using a pairing heap by default.
EppsteinKShortestPath<V,E>	Implementation of the Eppstein`s algorithm for finding $k$ shortest path between two vertices in a graph.
EppsteinShortestPathIterator<V,E>	Iterator over the shortest paths (not required to be simple) between two vertices in a graph sorted by weight.
FloydWarshallShortestPaths<V,E>	The Floyd-Warshall algorithm.
GraphMeasurer<V,E>	Algorithm class which computes a number of distance related metrics.
IntVertexDijkstraShortestPath<E>	Dijkstra Shortest Path implementation specialized for graphs with integer vertices.
JohnsonShortestPaths<V,E>	Johnson's all pairs shortest paths algorithm.
KShortestSimplePaths<V,E>	Deprecated. Use YenKShortestPath instead.
ListMultiObjectiveSingleSourcePathsImpl<V,E>	An implementation of MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths which stores one list of paths per vertex.
ListSingleSourcePathsImpl<V,E>	An implementation of ShortestPathAlgorithm.SingleSourcePaths which stores one path per vertex.
MartinShortestPath<V,E>	Martin's algorithm for the multi-objective shortest paths problem.
SuurballeKDisjointShortestPaths<V,E>	An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths.
TreeMeasurer<V,E>	Algorithm class which computes a number of distance related metrics for trees.
TreeSingleSourcePathsImpl<V,E>	An implementation of ShortestPathAlgorithm.SingleSourcePaths which uses linear space.
YenKShortestPath<V,E>	Implementation of Yen`s algorithm for finding $k$ shortest loopless paths.
YenShortestPathIterator<V,E>	Iterator over the shortest loopless paths between two vertices in a graph sorted by weight.

Exception Summary

Exception	Description
NegativeCycleDetectedException	An exception used to notify about the detection of a negative cycle.