Bellman Ford Algorithm Claims
Разница между en2 и en3, 155 символ(ов) изменены
I had been solving [High Score](https://cses.fi/problemset/task/1673/) problem. After reading [some](https://codeforces.net/blog/entry/79981) [blogs](https://cp-algorithms.com/graph/bellman_ford.html), I was able to conclude:</ <br/>↵


<b>
Claim 1:</b> Consider ALL```ALL``` cycles ```{ C(i) }``` reachable from source S```S```. In the Bellman Ford Algorithm, ```FOR EVERY``` cycle ```C(i)```,</br>↵
 ```THERE EXISTS A (```  a vertex) in ```C(i)``` whose distance is modified in the ```nth``` iteration of the Algorithm)↵

<b>
Claim 2:</b> If the distance if a vertex is modified in the (nth```nth``` iteration), it must be the part of a negative cycle</br>


Can someone please verify if T```these Cclaims``` are correct? </br/>↵

The Solution idea to [High Score](https://cses.fi/problemset/task/1673/)<
/br/>↵
Multiply all edge weights by ```-1```, now we need to minimize our score<
/br/>↵
S: Source Vertex<
/br />↵
D: Destination Vertex <
/br />↵
C: A negative weight directed cycle<
/brbr /><br />↵
```IF:```<
/br/>↵
* 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 <
/br/>↵
```ELSE:```<
/br/>↵
* There must exist a negative weight cycle reachable from ```S```. But this does not imply that the Minimum Score to reach ```D``` is ```-INFINITY```<
/br/>↵
==> 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.<
/br/>↵
* 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```. <
/br/>↵
** If```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 the ```nth``` ( or ```(n-1)th``` ) iteration</br/>↵
All test cases passed<
/br/>↵
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.<
/br/>↵





 

История

 
 
 
 
Правки
 
 
  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)