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
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
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>The algorithm determines the k shortest simple paths in increasing order of weight. ListMultiObjectiveSingleSourcePathsImpl<V,E>An implementation of
MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePathswhich stores one list of paths per vertex.
ListSingleSourcePathsImpl<V,E>An implementation of
ShortestPathAlgorithm.SingleSourcePathswhich 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.SingleSourcePathswhich 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 NegativeCycleDetectedExceptionAn exception used to notify about the detection of a negative cycle.