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

Parameters:

GNetworkX graph

sourcenode

Starting node for path

targetnode

Ending node for path

weightstring or function

If it is a string, it is the name of the edge attribute to be used as a weight.

If it is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None. The weight function can be used to hide edges by returning None. So weight = lambda u, v, d: 1 if d['color']=="red" else None will find the shortest red path.

If None all edges are considered to have unit weight. Default value None.

Returns:

path_generator: generator: A generator that produces lists of simple paths, in order from shortest to longest.

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.

See also

all_shortest_paths
shortest_path
all_simple_paths

Notes

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

References

[1]

Jin Y. Yen, “Finding the K Shortest Loopless Paths in a Network”, Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 712-716.

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]