Bellman Ford's prev doesn't get properly updated #300
Description
I've noticed that it's possible for a spot to have -inf distance but -1 as prev. I believe this is due to how a reduced number of iterations are performed followed by an extra loop at the end to propagate -inf.
I believe making this modification would fix it, but I wanted to get additional feedback on this before proposing it (in case some of the optimizations applied would lead to this not fully resolving the issue):
rep(i,0,lim) for (Ed e : eds) {
- if (nodes[e.a].dist == -inf)
+ if (nodes[e.a].dist == -inf) {
+ nodes[e.b].prev = e.a;
nodes[e.b].dist = -inf;
+ }
}