Zero-weight cycle problem

In computer science and graph theory, the zero-weight cycle problem is the problem of deciding whether a directed graph with weights on the edges (which may be positive or negative or zero) has a cycle in which the sum of weights is 0.

This related problem can be solved in polynomial time using the Bellman–Ford algorithm.

If there is no negative cycle, then the distances found by the Bellman–Ford algorithm can be used, as in Johnson's algorithm, to reweight the edges of the graph in such a way that all edge weights become non-negative and all cycle lengths remain unchanged.

[1] This is true even when the weights are integers of polynomial magnitude.

, to the zero-weight cycle problem on a weighted graph obtained by giving all edges of

weight equal to one, and adding an additional edge from