If we are given a graph, Now from source we are to calculate the shortest path. Now , If an edge has a negative weight , but there is edge to back-edge to get back to that edge while reaching the destination I mean if there is no cycle, then we don't have a negative cycle. But the here in Wikipedia the given algorithm which runs from source again thus it detects a negative edge weight but not a negative cycle. My Question is, How to determine a negative cycle?
12 Answers
A negative weight cycle is a cycle with weights that sum to a negative number. The Bellman-Ford algorithm propagates correct distance estimates to all nodes in a graph in V-1 steps, unless there is a negative weight cycle. If there is a negative weight cycle, you can go on relaxing its nodes indefinitely. Therefore, the ability to relax an edge after V-1 steps is a test for the presence of a negative weight cycle, as seen in the Wikipedia algorithm. So the Bellman-Ford algorithm tests for negative weight cycles.
You can refer this link for determining actual negative cycle. In last iteration of the algo . We only get to know about the effected node . affected because of negative cycle. The actual negative cycle forms a infinite loop of parent[parent[parent].
Second loop of the code is like throwing a pinball from the top, after some time the ball revolves around a circular maze infinitely. We find that circular maze.
