Timeline for Bellman Ford facts and specific question
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 16, 2021 at 11:04 | comment | added | Massimo Cafaro | What you mean exactly by "clean comments" ? | |
| Jan 16, 2021 at 7:26 | vote | accept | Okh. Pij | ||
| Jan 7, 2021 at 9:55 | comment | added | Massimo Cafaro | Your counter-example is wrong: in $k$ iterations the algorithm is only considering paths of length $k$. Try running BF and you will se that after 2 iterations only the paths $s$-->$t$ and $s$-->$u$ have been correctly computed (the distance for $s$-->$v$ will still be $\infty$). | |
| Jan 6, 2021 at 17:14 | comment | added | Massimo Cafaro | The link you provide has two questions. The first one is exactly the one which I have answered, providing full details: besides the standard induction proof there is nothing that can be really usefully added. The second claim, the one related to the weights on a shortest paths is obviously false, as already shown in the answer to the question you linked to. Regarding the variants available in Jeff Erickson's book, the first is just a minor variation due to Moore (which is faster) and the other three are just the steps needed to simplify the original algorithm based on dynamic programming. | |
| Jan 6, 2021 at 15:09 | comment | added | Massimo Cafaro | in your original question there is no reference to a modified algorithm. The answer refers to the Bellman Ford original algorithm. By the way, the example given in your comment can not be understood, since you are not providing the full input graph and the weights on each of the edges. | |
| Dec 9, 2020 at 7:37 | history | edited | Massimo Cafaro | CC BY-SA 4.0 | added 71 characters in body |
| Dec 8, 2020 at 11:33 | history | answered | Massimo Cafaro | CC BY-SA 4.0 |