Relaxation

Technique used in algorithms such as Dijkstra’s Algorithm and Bellman-Ford Algorithm to update the path to a shorter one.

In which approximations to the correct distance are replaced by better ones until they eventually reach the solution.

Bellman-Ford Relaxation

In order to detect whether a negative cycle exists or not, relax all the edge one more time and if the shortest distance for any node reduces then we can say that a negative cycle exists.

In short if we relax the edges N times, and there is any change in the shortest distance of any node between the N-1-th and N-th relaxation than a negative cycle exists, otherwise not exist.