graph_tool.topology.shortest_path(g, source, target, weights=None, negative_weights=False, pred_map=None, dag=False)[source]#

Return the shortest path from source to target.


Graph to be used.


Source vertex of the search.


Target vertex of the search.

weightsEdgePropertyMap (optional, default: None)

The edge weights.

negative_weightsbool (optional, default: False)

If True, this will trigger the use of the Bellman-Ford algorithm.

pred_mapVertexPropertyMap (optional, default: None)

Vertex property map with the predecessors in the search tree. If this is provided, the shortest paths are not computed, and are obtained directly from this map.

dagbool (optional, default:False)

If True, assume that the graph is a Directed Acyclic Graph (DAG), which will be faster if weights are given, in which case they are also allowed to contain negative values (irrespective of the parameter negative_weights).

vertex_listlist of Vertex

List of vertices from source to target in the shortest path.

edge_listlist of Edge

List of edges from source to target in the shortest path.


The paths are computed with a breadth-first search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given. If negative_weights == True, the Bellman-Ford algorithm is used [bellman-ford], which accepts negative weights, as long as there are no negative loops.

The algorithm runs in \(O(V + E)\) time, or \(O(V \log V)\) if weights are given (if dag == True this improves to \(O(V+E)\)).



Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press


E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269-271, 1959.


>>> from numpy.random import poisson
>>> g = gt.random_graph(300, lambda: (poisson(4), poisson(4)))
>>> vlist, elist = gt.shortest_path(g, g.vertex(10), g.vertex(11))
>>> print([str(v) for v in vlist])
['10', '33', '63', '292', '11']
>>> print([str(e) for e in elist])
['(10, 33)', '(33, 63)', '(63, 292)', '(292, 11)']