shortest_simple_paths¶

shortest_simple_paths(G, source, target, weight=None)[source]¶

Generate all simple paths in the graph G from source to target,: starting from shortest ones.

A simple path is a path with no repeated nodes.

If a weighted shortest path search is to be used, no negative weights are allawed.

Parameters:	G (NetworkX graph) – source (node) – Starting node for path target (node) – Ending node for path weight (string) – Name of the edge attribute to be used as a weight. If None all edges are considered to have unit weight. Default value None.
Returns:	path_generator – A generator that produces lists of simple paths, in order from shortest to longest.
Return type:	generator
Raises:	`NetworkXNoPath` – If no path exists between source and target. `NetworkXError` – If source or target nodes are not in the input graph. `NetworkXNotImplemented` – If the input graph is a Multi[Di]Graph.

Examples

>>> G = nx.cycle_graph(7)
>>> paths = list(nx.shortest_simple_paths(G, 0, 3))
>>> print(paths)
[[0, 1, 2, 3], [0, 6, 5, 4, 3]]

You can use this function to efficiently compute the k shortest/best paths between two nodes.

>>> from itertools import islice
>>> def k_shortest_paths(G, source, target, k, weight=None):
...     return list(islice(nx.shortest_simple_paths(G, source, target, weight=weight), k))
>>> for path in k_shortest_paths(G, 0, 3, 2):
...     print(path)
[0, 1, 2, 3]
[0, 6, 5, 4, 3]

Notes

This procedure is based on algorithm by Jin Y. Yen [1]. Finding the first K paths requires O(KN^3) operations.