Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
bellman_ford¶
- bellman_ford(G, source, weight='weight')[source]¶
Compute shortest path lengths and predecessors on shortest paths in weighted graphs.
The algorithm has a running time of O(mn) where n is the number of nodes and m is the number of edges. It is slower than Dijkstra but can handle negative edge weights.
Parameters : G : NetworkX graph
The algorithm works for all types of graphs, including directed graphs and multigraphs.
source: node label
Starting node for path
weight: string, optional (default=’weight’)
Edge data key corresponding to the edge weight
Returns : pred, dist : dictionaries
Returns two dictionaries keyed by node to predecessor in the path and to the distance from the source respectively.
Raises : NetworkXUnbounded
If the (di)graph contains a negative cost (di)cycle, the algorithm raises an exception to indicate the presence of the negative cost (di)cycle. Note: any negative weight edge in an undirected graph is a negative cost cycle.
Notes
Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.
The dictionaries returned only have keys for nodes reachable from the source.
In the case where the (di)graph is not connected, if a component not containing the source contains a negative cost (di)cycle, it will not be detected.
Examples
>>> import networkx as nx >>> G = nx.path_graph(5, create_using = nx.DiGraph()) >>> pred, dist = nx.bellman_ford(G, 0) >>> sorted(pred.items()) [(0, None), (1, 0), (2, 1), (3, 2), (4, 3)] >>> sorted(dist.items()) [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
>>> from nose.tools import assert_raises >>> G = nx.cycle_graph(5, create_using = nx.DiGraph()) >>> G[1][2]['weight'] = -7 >>> assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, 0)