Bellman-Ford Algorithm Short predecessor Array

Question

Having this Algorithm of Bellman-Ford with a slight change: In line 7, instead of the inequality sign, we put >= so it becomes: d[v] >= d[u] + w(u,v)

Now I know for a fact that it will not change the distances array and it will give me a correct answer. But how will it affect my predecessor array on line 9? will it still give a correct answer?

Answer 1

If you have non positive edges it may not be a tree, for example for the following graph and starting from n1:

In the first pass:

• by visiting e1: d[n2] = d[n1] + w[e1] = 1 & p[n2] = n1
• by visiting e2: d[n3] = d[n2] + w[e2] = 1 & p[n3] = n2
• by visiting e3: d[n4] = d[n3] + w[e3] = 1 & p[n4] = n3
• by visiting e4: d[n2] = d[n4] + w[e4] = 1 & p[n2] = n4

and in all remaining passes, this will repeat. so at the end if you iterate over predecessor for example for n2 your will get: n2 <- n4 <- n3 <- n2 <- n4 <- ...

But I think if you don't have non-negative edges it works fine.