- shortest_path(G, source=None, target=None, weight=None, method='dijkstra')[source]#
Compute shortest paths in the graph.
- GNetworkX graph
- sourcenode, optional
Starting node for path. If not specified, compute shortest paths for each possible starting node.
- targetnode, optional
Ending node for path. If not specified, compute shortest paths to all possible nodes.
- weightNone, string or function, optional (default = None)
If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1. If this 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.
- methodstring, optional (default = ‘dijkstra’)
The algorithm to use to compute the path. Supported options: ‘dijkstra’, ‘bellman-ford’. Other inputs produce a ValueError. If
weightis None, unweighted graph methods are used, and this suggestion is ignored.
- path: list or dictionary
All returned paths include both the source and target in the path.
If the source and target are both specified, return a single list of nodes in a shortest path from the source to the target.
If only the source is specified, return a dictionary keyed by targets with a list of nodes in a shortest path from the source to one of the targets.
If only the target is specified, return a dictionary keyed by sources with a list of nodes in a shortest path from one of the sources to the target.
If neither the source nor target are specified return a dictionary of dictionaries with path[source][target]=[list of nodes in path].
sourceis not in
methodis not among the supported options.
There may be more than one shortest path between a source and target. This returns only one of them.
>>> G = nx.path_graph(5) >>> print(nx.shortest_path(G, source=0, target=4)) [0, 1, 2, 3, 4] >>> p = nx.shortest_path(G, source=0) # target not specified >>> p # shortest path from source=0 to target=3 [0, 1, 2, 3] >>> p = nx.shortest_path(G, target=4) # source not specified >>> p # shortest path from source=1 to target=4 [1, 2, 3, 4] >>> p = nx.shortest_path(G) # source, target not specified >>> p # shortest path from source=2 to target=4 [2, 3, 4]