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.