Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

all_pairs_dijkstra_path_length

all_pairs_dijkstra_path_length(G, cutoff=None, weight='weight')[source]

Compute shortest path lengths between all nodes in a weighted graph.

Parameters:

G : NetworkX graph

weight: string, optional (default=’weight’)

Edge data key corresponding to the edge weight

cutoff : integer or float, optional

Depth to stop the search. Only paths of length <= cutoff are returned.

Returns:

distance : dictionary

Dictionary, keyed by source and target, of shortest path lengths.

Notes

Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

The dictionary returned only has keys for reachable node pairs.

Examples

>>> G=nx.path_graph(5)
>>> length=nx.all_pairs_dijkstra_path_length(G)
>>> print(length[1][4])
3
>>> length[1]
{0: 1, 1: 0, 2: 1, 3: 2, 4: 3}