NetworkX

Previous topic

networkx.shortest_path

Next topic

networkx.average_shortest_path_length

networkx.shortest_path_length

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

Compute shortest path lengths in the graph.

This function can compute the single source shortest path lengths by specifying only the source or all pairs shortest path lengths by specifying neither the source or target.

Parameters:

G : NetworkX graph

source : node, optional

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

target : node, optional

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

weighted : bool, optional

If True consider weighted edges when finding shortest path length.

Returns:

length : number, or container of numbers

If the source and target are both specified return a single number for the shortest path. If only the source is specified return a dictionary keyed by targets with a the shortest path as keys. If neither the source or target is specified return a dictionary of dictionaries with length[source][target]=value.

Raises:

NetworkXError :

If no path exists between source and target.

Notes

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

For digraphs this returns the shortest directed path. To find path lengths 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_length(G,source=0,target=4)
4
>>> p=nx.shortest_path_length(G,source=0) # target not specified
>>> p[4]
4
>>> p=nx.shortest_path_length(G) # source,target not specified
>>> p[0][4]
4