networkx.algorithms.simple_paths.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.
See also
all_shortest_paths()
,shortest_path()
,all_simple_paths()
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.