Warning

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

# networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford¶

single_source_bellman_ford(G, source, target=None, weight='weight')[source]

Compute shortest paths and lengths in a weighted graph G.

Uses Bellman-Ford algorithm for shortest paths.

Parameters: G (NetworkX graph) source (node label) – Starting node for path target (node label, optional) – Ending node for path distance, path – If target is None, returns a tuple of two dictionaries keyed by node. The first dictionary stores distance from one of the source nodes. The second stores the path from one of the sources to that node. If target is not None, returns a tuple of (distance, path) where distance is the distance from source to target and path is a list representing the path from source to target. pair of dictionaries, or numeric and list NodeNotFound – If source is not in G.

Examples

>>> G = nx.path_graph(5)
>>> length, path = nx.single_source_bellman_ford(G, 0)
>>> print(length[4])
4
>>> for node in [0, 1, 2, 3, 4]:
...     print('{}: {}'.format(node, length[node]))
0: 0
1: 1
2: 2
3: 3
4: 4
>>> path[4]
[0, 1, 2, 3, 4]
>>> length, path = nx.single_source_bellman_ford(G, 0, 1)
>>> length
1
>>> path
[0, 1]


Notes

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