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)

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

a GraphPath

jgrapht.algorithms.shortestpaths.a_star_with_alt_heuristic(graph, source_vertex, target_vertex, landmarks, use_bidirectional=False)

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 non-negative edge weights. The heuristic requires a set of input nodes from the graph, which are used as landmarks. During a pre-processing 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 triangle-inequality. 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 ACM-SIAM symposium on Discrete algorithms (SODA’ 05), 156–165, 2005.

Note that using this heuristic does not require the edge weights to satisfy the triangle-inequality. 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

a GraphPath

jgrapht.algorithms.shortestpaths.bellman_ford(graph, source_vertex)

Bellman-Ford algorithm to compute single-source shortest paths.

Computes shortest paths from a single source vertex to all other vertices in a weighted graph. The Bellman-Ford 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)

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)

Delta stepping algorithm to compute single-source 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 or SingleSourcePaths depending on whether a target vertex is provided

jgrapht.algorithms.shortestpaths.dijkstra(graph, source_vertex, target_vertex=None, use_bidirectional=True)

Dijkstra’s algorithm to compute single-source 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 or SingleSourcePaths depending on whether a target vertex is provided

jgrapht.algorithms.shortestpaths.eppstein_k(graph, source_vertex, target_vertex, k)

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)

The Floyd-Warshall algorithm for all-pairs shortest-paths.

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

all-pairs shortest paths as an instance of AllPairsPaths

jgrapht.algorithms.shortestpaths.johnson_allpairs(graph)

Johnson’s all-pairs shortest-paths algorithm.

Finds the shortest paths between all pairs of vertices in a sparse graph. Edge weights can be negative, but no negative-weight cycles may exist. It first executes the Bellman-Ford 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

all-pairs shortest paths as an instance of AllPairsPaths

jgrapht.algorithms.shortestpaths.martin_multiobjective(graph, edge_weight_cb, edge_weight_dimension, source_vertex, target_vertex=None)

Martin’s algorithm for the multi-objective 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 non-negative.

Note

Note that the multi-objective shortest path problem is a well-known NP-hard 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 or MultiObjectiveSingleSourcePaths depending on whether a target vertex is provided

jgrapht.algorithms.shortestpaths.yen_k_loopless(graph, source_vertex, target_vertex, k)

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. 121-133.

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

Interface for a graph path.

abstract edges()

Edges of the path.

Return type

collections.abc.Iterable

abstract end_vertex()

Ending vertex of the path.

abstract graph()

The graph that this graph path refers to.

Return type

jgrapht.types.Graph

abstract start_vertex()

Starting vertex of the path.

property vertices

Vertices of the path.

abstract weight()

Weight of the path.

Return type

Double

class jgrapht.types.SingleSourcePaths

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.

abstract get_path(target_vertex)

Get a path to a target vertex.

Parameters

target_vertex – The target vertex.

Returns

a path from the source to the target vertex.

abstract source_vertex()

The source vertex.

class jgrapht.types.AllPairsPaths

Paths between all pair of vertices. Used in all-pair shortest path algorithms in order to represent the result set.

abstract get_path(source_vertex, target_vertex)

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

GraphPath

abstract get_paths_from(source_vertex)

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

class jgrapht.types.MultiObjectiveSingleSourcePaths

A set of paths starting from a single source vertex.

abstract get_paths(target_vertex)

Get the set of paths to the target vertex.

Parameters

target_vertex – The target vertex.

Returns

an iterator over all paths from the source to the target vertex

abstract source_vertex()

The source vertex.