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 byKShortestSimplePaths
- 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 fromgraph
.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 usingDijkstraClosestFirstIterator
.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 ofMultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths
which stores one list of paths per vertex.ListSingleSourcePathsImpl<V,E> An implementation ofShortestPathAlgorithm.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 ofShortestPathAlgorithm.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.