Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
package org.jgrapht.alg.shortestpath
Shortest-path related algorithms.
-
ClassDescriptionAllDirectedPaths<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.An admissible heuristic for the A* algorithm using a set of landmarks and the triangle inequality.AStarShortestPath<V,E> A* shortest path.Base class for the bidirectional shortest path algorithms.Base class of the search frontier used by bidirectional shortest path algorithms.A base implementation of a $k$ disjoint shortest paths algorithm based on the strategy used in Suurballe and Bhandari algorithms.Base class for many-to-many shortest paths algorithms.A base implementation of the multi-objective shortest path interface.A base implementation of the shortest path interface.The Bellman-Ford algorithm.BFSShortestPath<V,E> The BFS Shortest Path algorithm.An implementation of Bhandari algorithm for finding $K$ edge-disjoint shortest paths.A bidirectional version of A* algorithm.A bidirectional version of Dijkstra's algorithm.Maintains search frontier during shortest path computation.Efficient algorithm for the many-to-many shortest paths problem based on contraction hierarchy.Implementation of the hierarchical query algorithm based on the bidirectional Dijkstra search.Maintains search frontier during shortest path computation.Parallel implementation of the contraction hierarchy route planning precomputation technique.Edge for building the contraction hierarchy.Return type of this algorithm.Vertex for building the contraction hierarchy, which contains an original vertex fromgraph
.Contains information of a vertex needed during the contraction.Contains statistics corresponding to a vertex incontractionGraph
needed to compute its priority.Naive algorithm for many-to-many shortest paths problem using.Implementation of theManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths
.Parallel implementation of a single-source shortest path algorithm: the delta-stepping algorithm.A light-weight version of the closest-first iterator for a directed or undirected graphs.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.Implementation of the Eppstein`s algorithm for finding $k$ shortest path between two vertices in a graph.Iterator over the shortest paths (not required to be simple) between two vertices in a graph sorted by weight.The Floyd-Warshall algorithm.GraphMeasurer<V,E> Algorithm class which computes a number of distance related metrics.Dijkstra Shortest Path implementation specialized for graphs with integer vertices.JohnsonShortestPaths<V,E> Johnson's all pairs shortest paths algorithm.An implementation ofMultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths
which stores one list of paths per vertex.An implementation ofShortestPathAlgorithm.SingleSourcePaths
which stores one path per vertex.MartinShortestPath<V,E> Martin's algorithm for the multi-objective shortest paths problem.An exception used to notify about the detection of a negative cycle.PathValidator<V,E> Path validator for shortest path algorithms.An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths.Parallel implementation of the transit node routing route planning precomputation technique.Forward or backward access vertex computed for a certain vertex $v$ in the graph.Stores forward and backward access vertices computed for the transit node routing.Search space based locality filter.This class represents return type of this algorithm and contains all data computed during the execution of the algorithm.Voronoi diagram for a graph.Implementation of the shortest paths algorithm based onTransitNodeRoutingPrecomputation
.TreeMeasurer<V,E> Algorithm class which computes a number of distance related metrics for trees.An implementation ofShortestPathAlgorithm.SingleSourcePaths
which uses linear space.YenKShortestPath<V,E> Implementation of Yen`s algorithm for finding $k$ shortest loopless paths.Iterator over the shortest loopless paths between two vertices in a graph sorted by weight.