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


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.

  • 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.

Return type:

pair of dictionaries, or numeric and list


NodeNotFound – If source is not in G.


>>> G = nx.path_graph(5)
>>> length, path = nx.single_source_bellman_ford(G, 0)
>>> print(length[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
>>> path
[0, 1]


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