Warning

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

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 – Returns two dictionaries representing a list of predecessors of a node and the distance to each node.

Return type:

dictionaries

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.