Warning

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

goldberg_radzik(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 or function) – If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.edges[u, v][weight]). If no such edge attribute exists, the weight of the edge is assumed to be one. If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number. pred, dist – Returns two dictionaries keyed by node to predecessor in the path and to the distance from the source respectively. dictionaries NodeNotFound – If source is not in G. 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.

Examples

>>> import networkx as nx
>>> G = nx.path_graph(5, create_using = nx.DiGraph())
>>> pred, dist = nx.goldberg_radzik(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