Repository navigation
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;
+ }
}
Activity
ItsDeadlyProgrammer commentedon Oct 9, 2026
I've opened #325 with this fix (setting
prev = e.ain the propagation loop). It also adds a stress test for BellmanFord. On current main it finds-infnodes withprev = -1or with aprevwhose distance isn't-inf, and with the change all checks pass.JJCUBER commentedon Oct 9, 2026
Closing unless/until I recall what the edge case I ran into was since it seems like this doesn't really "fix" anything per se.