I had been solving High Score problem. After reading some blogs, I was able to conclude
Claim 1: Consider ALL negative cycles {C(i)} reachable from source S. In the Bellman Ford Algorithm, FOR EVERY cycle C(i), THERE EXISTS a vertex in C(i) whose distance is modified in the nth iteration of the Algorithm)
Claim 2: If the distance of a vertex is modified in the nth iteration, then it must be the part of a negative cycle
Can someone please verify if these claims are correct?
The Solution idea to High Score
Multiply all edge weights by -1, now we need to minimize our score
S: Source Vertex
D: Destination Vertex
C: A negative weight directed cycle
IF:
* In the nth iteration if there does not occur any relaxation for any edge, then there is no negative cycle reachable from S hence the answer dist(D) from Bellman Ford is the Correct answer
ELSE:
* There must exist a negative weight cycle reachable from S. But this does not imply that the Minimum Score to reach D is -INFINITY
==> It is possible that if we enter the cycle C, it is not possible to reach D so it we can't keep reducing our score by cycling through the cycle.
* So we need to check if there exits a negative weight cycle C such that it is possible to reach C from S and then reach D from C.
If such a C exists, the minimum score to reach D from S is -INFINITY
Else bellman ford Gave us th ecorrect answer after the nth ( or (n-1)th) iteration
All test cases passed
Could solmeone Acknowledge if Claim 1 and Claim 2 are correct? I believe they need to be for the correctness of the above mentioned solution.
Claim 2 is true. But claim 1 is only true for negative cycles.
This is because in the x(th) iteration of the bellman ford algorithm, the algorithm finds shortest paths from source vertex to all other vertices such that you take use x edges in total, then updates the values if it is smaller then the previous value.
Therefore, if the algorithm changes a distance to vertex in the nth iteration (where there are n vertices), then it means that the optimal path takes n edges, so it visits n+1 vertices. This means that it visits one vertex at least twice. Notice that it doesn't make sense to visit the same vertex twice unless it is a negative cycle — so ur second claim is true.
Following this logic, if a cycle exists, then by taking n edges, exactly one of vertices in the cycle will complete the negative cycle, so its value will be changed. This logic does not hold if the cycle is of positive length as if if it is a positive cycle, then completing the cycle will result in a longer path and the vertex will not be updated.
Yes! Sorry that was an error, I meant all negative cycles
Can you elaborate please? How did you prove that the vertex, "whose" distance was modified in the nth iteration is part of a negatie cycle
Auto comment: topic has been updated by frying_pan (previous revision, new revision, compare).
Claim 1 is correct, but Claim 2 is wrong. Distance change only means there is a negative cycle on a path between source and this vertex. At this example vertex B doesn't lay on any cycle, however its distance from S will infinitely decrease via Ford-Bellman relaxation process.