dijkstra_predecessor_and_distance¶

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

Compute shortest path length and predecessors on shortest paths in weighted graphs.

Parameters :

G : NetworkX graph

source : node label

Starting node for path

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 :

pred,distance : dictionaries

Returns two dictionaries representing a list of predecessors of a node and the distance to each node.

Notes

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

The list of predecessors contains more than one element only when there are more than one shortest paths to the key node.