shortest_path

Contents

shortest_path#

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.

Parameters:
gGraph

Graph to be used.

sourceVertex

Source vertex of the search.

targetVertex

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).

Returns:
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.

Notes

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)\)).

References

[bfs]

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

[dijkstra]

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

Examples

>>> 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', '114', '96', '97', '11']
>>> print([str(e) for e in elist])
['(10, 114)', '(114, 96)', '(96, 97)', '(97, 11)']
Contents