# Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure have computed shortest paths with $k$ length. However, the part that I don't quite understand is why not only relaxing the edges that are directly connected to the source on the first iteration and then the neighbors' edges of those on the second iteration, and then the neighbouring eges of those and so forth?

The idea, is a similar algorithm to BFS I guess. We start from the frontier of edges relaxed and we make sure that we are connected to a node that we have computed its shortest path and since we are always relaxing edges that are connected like that, then we compute the shortest path in 1 pass rather than $O(EV)$ passes. I am sure I am wrong but I don't understand why. Of course it works in a straight line graph, but what type of worst-case input does it make that we need about at least $\Omega(EV)$?

I am mostly interested to understand, is the EV runtime in the worst case. I also do not care about improvements in practice or constant factors. Only asymptotics.

• I find it hard to follow your algorithmic idea. Please give pseudocode. If it is too similar to BFS then no, it won't work; it's easy to give counter examples for BFS (even without negative weights, which BF handles just fine).
– Raphael
Apr 13, 2016 at 8:09

However, it doesn't help much. It doesn't change the asymptotic running time of the algorithm. In many graphs, after about $O(\lg n)$ iterations, essentially every vertex is reachable from the starting point. Therefore, you might save a little bit on the first $O(\lg n)$ iterations, but after that, you still have to relax all edges. Thus, this makes only a minor improvement -- far too small to show up in the asymptotic running time. And, in practice, on most graphs, the improvement will probably be small -- perhaps so small as to be outweighed by the extra bookkeeping required.
The minor modification you need to make is: in the $k$th iteration, relax all edges $(u,v)$ where $u$ is at most $k$ edges from the source [rather than where $u$ is exactly $k$ edges away from the source]. This is important, because the shortest path from $s$ to $u$ (the one where the sum of the distances on the edges in the path) need not be the same as the path from $s$ to $u$ with the fewest edges.
• @Pinocchio D.W. explains the exact opposite: in many graphs, you end up with $\Theta(EV)$ anyway but have a way more complicated algorithm. (You also need to track which vertices to touch in every iteration.) That said, I don't know if D.W. understood your proposal correctly.