Package com.jgalgo.alg.shortestpath

Algorithms for finding paths in graphs, such as shortest paths, iterating over all simple paths between two vertices, computing the Voronoi cells given a set of sites, ect.

Interface Summary

Interface	Description
KShortestPathsSt	An algorithm for computing the K shortest paths between two vertices in a graph.
ShortestPathAllPairs	An algorithm that compute all pairs shortest path (APSP) in a graph.
ShortestPathAllPairs.Builder	A builder for ShortestPathAllPairs objects.
ShortestPathAllPairs.IResult	A result object for an ShortestPathAllPairs algorithm for IntGraph.
ShortestPathAllPairs.Result<V,E>	A result object for an ShortestPathAllPairs algorithm.
ShortestPathHeuristicSt	Shortest path algorithm that uses a distance heuristic function.
ShortestPathSingleSource	Single Source Shortest Path algorithm.
ShortestPathSingleSource.Builder	A builder for ShortestPathSingleSource objects.
ShortestPathSingleSource.IResult	A result object for the ShortestPathSingleSource problem for IntGraph.
ShortestPathSingleSource.Result<V,E>	A result object for the ShortestPathSingleSource problem.
ShortestPathSt	An algorithm for computing the shortest path between two vertices in a graph.
SimplePathsEnumerator	An algorithm that enumerate over simple paths between a source and a target.
Tsp	Traveling Salesman Problem (TSP) algorithm.
VoronoiAlgo	Voronoi cells algorithm.
VoronoiAlgo.IResult	A result object of VoronoiAlgo computation for IntGraph.
VoronoiAlgo.Result<V,E>	A result object of VoronoiAlgo computation.

Class Summary

Class	Description
KShortestPathsStAbstract	Abstract class for computing the k-shortest paths in graphs.
KShortestPathsStBasedPathsTree	A base class for computing the k-shortest paths from a source vertex to a target vertex in a graph using the compressed paths tree data structure.
KShortestPathsStHershbergerMaxelSuri	Hershberger, Maxel and Suri algorithm for K shortest simple paths in directed graphs.
KShortestPathsStKatohIbarakiMine	Katoh, Ibaraki and Mine algorithm for K shortest simple paths in undirected graphs.
KShortestPathsStYen	Yen's algorithm for computing the K shortest paths between two vertices in a graph.
ShortestPathAllPairsAbstract	Abstract class for computing shortest path between all pairs in a graph.
ShortestPathAllPairsCardinality	All pairs cardinality shortest path algorithm.
ShortestPathAllPairsFloydWarshall	The Floyd Warshall algorithm for all pairs shortest path.
ShortestPathAllPairsJohnson	Johnson's algorithm for all pairs shortest path.
ShortestPathAStar	A* shortest path algorithm.
ShortestPathHeuristicStAbstract	Abstract class for computing shortest path between a source and a target with a heuristic.
ShortestPathSingleSourceAbstract	Abstract class for computing shortest path from a single source in graphs.
ShortestPathSingleSourceBellmanFord	Bellman–Ford algorithm for Single Source Shortest Path (SSSP) with negative weights in directed graphs.
ShortestPathSingleSourceCardinality	Single Source Shortest Path for cardinality weight function.
ShortestPathSingleSourceDag	Linear Single Source Shortest Path (SSSP) algorithm for directed acyclic graphs (DAG).
ShortestPathSingleSourceDial	Dial's algorithm for Single Source Shortest Path for positive integer weights.
ShortestPathSingleSourceDijkstra	Dijkstra's algorithm for Single Source Shortest Path (SSSP).
ShortestPathSingleSourceGoldberg	Goldberg's SSSP algorithm for integer (positive and negative) weights on directed graphs.
ShortestPathStAbstract	Abstract class for computing a single shortest path between a source and a target.
ShortestPathStBidirectionalBfs	Compute the shortest path between a source and a target using bidirectional breadth-first search.
ShortestPathStBidirectionalDijkstra	Compute the shortest path between a source and a target using bidirectional Dijkstra's algorithm.
SimplePathsEnumeratorAbstract	Abstract class for enumerating all simple paths between a source and target vertices.
SimplePathsEnumeratorSedgewick	Sedgewick's simple paths enumerator implementation.
TspAbstract	Abstract class for computing the shortest tour that visit all vertices in a graph.
TspMetricMatchingAppx	TSP \(3/2\)-approximation using maximum matching.
TspMetricMstAppx	Metric TSP \(2\)-approximation using minimum spanning trees.
VoronoiAlgoAbstract	Abstract class for computing the Voronoi cells in a graph given a set of site vertices.
VoronoiAlgoDijkstra	Variant of Dijkstra algorithm that starts at multiple vertices and compute the Voronoi cells.

Exception Summary

Exception	Description
NegativeCycleException	Exception thrown when a negative cycle is detected in a graph during a shortest path computation.