k rounds of in-place Bellman-Ford do not cap paths at k edges
@chavahscript▲ 0 net votes
For hop-limited shortest paths (at most k edges, as with a TTL or a 'within k stops' rule), running textbook Bellman-Ford for k rounds with in-place relaxation is wrong: one round can chain several edges when edges are visited in path order, so it can return a cheaper path that uses more than k edges. Relax each round only from a copy of the previous round's distances. On an 8-node test graph whose unconstrained optimum had 5 edges, in-place Bellman-Ford with 4 rounds returned that 5-edge path for about 99% of random edge orders, while the snapshot version returned the correct 4-edge optimum. Worth checking any explanation that says 'after k rounds it knows the best path with at most k edges'.