Shortest Paths¶
Algorithms¶
All classic algorithms for shortest paths are provided. See below for details.

jgrapht.algorithms.shortestpaths.
a_star
(graph, source_vertex, target_vertex, heuristic_cb, use_bidirectional=False)[source] The A* algorithm.
 Parameters
graph – the graph
source_vertex – the source vertex
target_vertex – the target vertex.
heuristic_cb – the heuristic callback. Must be a function which accepts two long parameters (source and target) and returns a double
use_bidirectional – use a bidirectional search
 Returns

jgrapht.algorithms.shortestpaths.
a_star_with_alt_heuristic
(graph, source_vertex, target_vertex, landmarks, use_bidirectional=False)[source] The A* algorithm with the ALT admissible heuristic.
The ALT admissible heuristic for the A* algorithm using a set of landmarks and the triangle inequality. Assumes that the graph contains nonnegative edge weights. The heuristic requires a set of input nodes from the graph, which are used as landmarks. During a preprocessing phase, which requires two shortest path computations per landmark using Dijkstra’s algorithm, all distances to and from these landmark nodes are computed and stored. Afterwards the heuristic estimates the distance from a vertex to another vertex using the already computed distances to and from the landmarks and the fact that shortest path distances obey the triangleinequality. The heuristic’s space requirement is \(\mathcal{O}(n)\) per landmark where \(n\) is the number of vertices of the graph. In case of undirected graphs only one Dijkstra’s algorithm execution is performed per landmark.
The method generally abbreviated as ALT (from A*, Landmarks and Triangle inequality) is described in detail in the following paper which also contains a discussion on landmark selection strategies.
Andrew Goldberg and Chris Harrelson. Computing the shortest path: A* Search Meets Graph Theory. In Proceedings of the sixteenth annual ACMSIAM symposium on Discrete algorithms (SODA’ 05), 156–165, 2005.
Note that using this heuristic does not require the edge weights to satisfy the triangleinequality. The method depends on the triangle inequality with respect to the shortest path distances in the graph, not an embedding in Euclidean space or some other metric, which need not be present.
In general more landmarks will speed up A* but will need more space. Given an A* query with vertices source and target, a good landmark appears “before” source or “after” target where before and after are relative to the “direction” from source to target.
 Parameters
graph – the graph
source_vertex – the source vertex
target_vertex – the target vertex.
landmarks – set of graph vertices to use for landmarks
use_bidirectional – use a bidirectional search
 Returns

jgrapht.algorithms.shortestpaths.
bellman_ford
(graph, source_vertex)[source] BellmanFord algorithm to compute singlesource shortest paths.
Computes shortest paths from a single source vertex to all other vertices in a weighted graph. The BellmanFord algorithm supports negative edge weights.
Negative weight cycles are not allowed and will be reported by the algorithm by raising an error. This implies that negative edge weights are not allowed in undirected graphs. Note that the algorithm will not find negative weight cycles which are not reachable from the source vertex.
Running time \(\mathcal{O}(m n)\).
 Parameters
graph – the graph
source_vertex – the source vertex
 Returns
a shortest path tree as an instance of
SingleSourcePaths

jgrapht.algorithms.shortestpaths.
bfs
(graph, source_vertex)[source] The BFS as a shortest path algorithm. Even if the graph has weights, this algorithms treats the graph as unweighted.
Running time \(\mathcal{O}(n+m)\).
 Parameters
graph – the graph
source_vertex – the source vertex
 Returns
a shortest path tree as an instance of
SingleSourcePaths

jgrapht.algorithms.shortestpaths.
delta_stepping
(graph, source_vertex, target_vertex=None, delta=None, parallelism=None)[source] Delta stepping algorithm to compute singlesource shortest paths.
 Parameters
graph – the graph
source_vertex – the source vertex
target_vertex – the target vertex. If None then shortest paths to all vertices are computed and returned as an instance of
SingleSourcePaths
delta – the delta parameter. If None then it is automatically calculated, by traversing the graph at least once.
parallelism – amount of parallelism to use. If None the cpu cores are used
 Returns
either a
GraphPath
orSingleSourcePaths
depending on whether a target vertex is provided

jgrapht.algorithms.shortestpaths.
dijkstra
(graph, source_vertex, target_vertex=None, use_bidirectional=True)[source] Dijkstra’s algorithm to compute singlesource shortest paths.
This implementation uses a pairing heap.
 Parameters
graph – the graph
source_vertex – the source vertex
target_vertex – the target vertex. If None then shortest paths to all vertices are computed and returned as an instance of
SingleSourcePaths
use_bidirectional – only valid if a target vertex is supplied. In this case the search is bidirectional
 Returns
either a
GraphPath
orSingleSourcePaths
depending on whether a target vertex is provided

jgrapht.algorithms.shortestpaths.
eppstein_k
(graph, source_vertex, target_vertex, k)[source] Eppstein’s algorithm for k shortest paths (may contain loops).
Running time \(\mathcal{O}(m + n \log n + k \log k)\). Paths are produced in sorted order by weight.
Note
Paths are not guaranteed to be simple, i.e. many contains loops.
 Parameters
graph – the graph. Must be simple
source_vertex – the source vertex
target_vertex – the target vertex
k – how many paths to return
 Returns
a iterator of
GraphPath

jgrapht.algorithms.shortestpaths.
floyd_warshall_allpairs
(graph)[source] The FloydWarshall algorithm for allpairs shortestpaths.
Find all \(n^2\) shortest paths in time \(\mathcal{O}(n^3)\). Also requires \(\mathcal{O}(n^2)\) space.
 Parameters
graph – the input graph
 Returns
allpairs shortest paths as an instance of
AllPairsPaths

jgrapht.algorithms.shortestpaths.
johnson_allpairs
(graph)[source] Johnson’s allpairs shortestpaths algorithm.
Finds the shortest paths between all pairs of vertices in a sparse graph. Edge weights can be negative, but no negativeweight cycles may exist. It first executes the BellmanFord algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra’s algorithm to be used on the transformed graph.
Running time \(\mathcal{O}(n m + n^2 \log n)\).
 Parameters
graph – the input graph
 Returns
allpairs shortest paths as an instance of
AllPairsPaths

jgrapht.algorithms.shortestpaths.
martin_multiobjective
(graph, edge_weight_cb, edge_weight_dimension, source_vertex, target_vertex=None)[source] Martin’s algorithm for the multiobjective shortest paths problem.
Martin’s label setting algorithm is a multiple objective extension of Dijkstra’s algorithm, where the minimum operator is replaced by a dominance test. It computes a maximal complete set of efficient paths when all the weight values are nonnegative.
Note
Note that the multiobjective shortest path problem is a wellknown NPhard problem.
 Parameters
graph – the graph
edge_weight_cb – edge weight callback. It should accept an edge as a parameter and return a list of weights.
edge_weight_dimension – dimension of the edge weight function
source_vertex – the source vertex
target_vertex – the target vertex. If None the paths to all vertices are computed and returned as an instance of
MultiObjectiveSingleSourcePaths
 Returns
either an iterator of
GraphPath
orMultiObjectiveSingleSourcePaths
depending on whether a target vertex is provided

jgrapht.algorithms.shortestpaths.
yen_k_loopless
(graph, source_vertex, target_vertex, k)[source] Yen’s algorithm for k loopless shortest paths.
Running time \(\mathcal{O}(k n (m + n \log n))\).
The implementation follows:
Q. V. Martins, Ernesto and M. B. Pascoal, Marta. (2003). A new implementation of Yen’s ranking loopless paths algorithm. Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 1. 121133.
 Parameters
graph – the graph
source_vertex – the source vertex
target_vertex – the target vertex.
k – how many paths to return
 Returns
a iterator of
GraphPath
Types¶
The shortest path module contains the following classes for the representation of the shortest path queries. All methods related to shortest paths return instances from these classes.

class
jgrapht.types.
GraphPath
[source]¶ Interface for a graph path.

property
vertices
¶ Vertices of the path.

property

class
jgrapht.types.
SingleSourcePaths
[source]¶ A set of paths starting from a single source vertex.
This class represents the whole shortest path tree from a single source vertex to all other vertices in the graph.

class
jgrapht.types.
AllPairsPaths
[source]¶ Paths between all pair of vertices. Used in allpair shortest path algorithms in order to represent the result set.

abstract
get_path
(source_vertex, target_vertex)[source]¶ Get a path from a source vertex to a target vertex.
 Parameters
source_vertex – The source vertex
target_vertex – The target vertex
 Returns
A path from the source vertex to the target vertex
 Return type

abstract
get_paths_from
(source_vertex)[source]¶ Get all paths from a source vertex to all other vertices.
:param source_vertex the source vertex :returns: a set of paths starting from a single source vertex :rtype:
SingleSourcePaths

abstract

class
jgrapht.types.
MultiObjectiveSingleSourcePaths
[source]¶ A set of paths starting from a single source vertex.