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
Returns:	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.
Return type:	pair of dictionaries, or numeric and list
Raises:	`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.