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.