find_negative_cycle

find_negative_cycle(G, source, weight='weight')

Returns a cycle with negative total weight if it exists.

Bellman-Ford is used to find shortest_paths. That algorithm stops if there exists a negative cycle. This algorithm picks up from there and returns the found negative cycle.

The cycle consists of a list of nodes in the cycle order. The last node equals the first to make it a cycle. You can look up the edge weights in the original graph. In the case of multigraphs the relevant edge is the minimal weight edge between the nodes in the 2-tuple.

If the graph has no negative cycle, a NetworkXError is raised.

Parameters

GNetworkX graph

source: list of nodes

List of source nodes. The search starts from all of the source nodes in the list.

weightstring 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

cyclelist

A list of nodes in the order of the cycle found. The last node equals the first to indicate a cycle.

Raises

NetworkXError

If no negative cycle is found.