networkx.shortest_path

shortest_path(G, source=None, target=None, weighted=False)

Compute shortest paths in the graph.

Parameters:

G : NetworkX graph

source : node, optional

Starting node for path. If not specified compute shortest paths for all connected node pairs.

target : node, optional

Ending node for path. If not specified compute shortest paths for every node reachable from the source.

weighted : bool, optional

If True consider weighted edges when finding shortest path.

Returns:

path: list or dictionary :

If the source and target are both specified return a single list of nodes in a shortest path. If only the source is specified return a dictionary keyed by targets with a list of nodes in a shortest path. If neither the source or target is specified return a dictionary of dictionaries with path[source][target]=[list of nodes in path].

Notes

There may be more than one shortest path between a source and target. This returns only one of them.

If weighted=True and the graph has no ‘weight’ edge attribute the value 1 will be used.

For digraphs this returns a shortest directed path. To find paths in the reverse direction use G.reverse(copy=False) first to flip the edge orientation.

Examples

>>> 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[4]
[0, 1, 2, 3, 4]
>>> p=nx.shortest_path(G) # source,target not specified
>>> p[0][4]
[0, 1, 2, 3, 4]