Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

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.

Returns

pred, dist – Returns two dictionaries keyed by node to predecessor in the path and to the distance from the source respectively.

Return type

dictionaries

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

>>> 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)]

>>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
>>> G["weight"] = -7