Bellman Ford Algorithm Claims

Правка en2, от frying_pan, 2023-02-18 15:51:53

I had been solving High Score problem. After reading some blogs, I was able to conclude:

Claim 1: Consider ALL 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 if a vertex is modified in the (nth iteration), it must be the part of a negative cycle

Can someone 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 </br> ** Else, bellman ford Gave us th ecorrect answer after thenth( or(n-1)th) iteration</br> All test cases passed</br> Could solmeone Acknowledge ifClaim 1andClaim 2``` are correct? I believe they need to be for the correctness of the above mentioned solution.

Теги graphs, bellman ford, shortest path, proof

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский frying_pan 2023-02-18 16:27:17 17
en5 Английский frying_pan 2023-02-18 16:22:38 2 Tiny change: ' distance if a vertex' -> ' distance of a vertex'
en4 Английский frying_pan 2023-02-18 16:13:18 9 Tiny change: '```ALL``` cycles ``' -> '```ALL``` negative cycles ``' (published)
en3 Английский frying_pan 2023-02-18 16:06:27 155 Tiny change: '`-INFINITY </br>\n**' -> '`-INFINITY``` </br>\n**'
en2 Английский frying_pan 2023-02-18 15:51:53 302 Tiny change: 'ect answer\nELSE:\n*' -> 'ect answer </br>\nELSE:\n*' (saved to drafts)
en1 Английский frying_pan 2023-02-18 15:36:17 1854 Initial revision (published)