| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
The algorithm computes from one source vertex the whole thing.
If i want to detect negative cycles in a graph using bellman ford, if i assume vertex 1 as the source, and no edge comes out of the vertex 1 in that test set, it wont work.
how will you consider source vertex in these cases... to detect negative cycles
Asking for solutions..
If no edge comes out from source vertex, then it's not possible to reach any other vertex from this source. The algorithm will work as expected.
I want to run bellman ford to detect negative cycles in a graph, in that case how will i choose the source. as i cant see which should be the source from the test set
should i consider all vertices as source each time and run!?
You can set the initial distance to every node as 0 and run the algorithm. This will be the same as creating a dummy node that goes to every vertex in the graph with 0 cost and using it as source vertex.
Thank you so much!!
This logic works fine considering a source from which no edge comes out!! O:)
because in other sense all are the sources here when all are initially zero :p :p