patternMinor
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?
Viewed 0 times
whycanbellmantherelaxedgessourcepassneighboursrecursively
Problem
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.
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.
Solution
This would work, with a minor modification. In other words, the resulting algorithm would be correct: it would correctly compute distances.
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.
Finally, this makes the algorithm more complicated. From a pedagogical perspective, when the purpose is to teach algorithms, unnecessary complications are best avoided, as they just make it harder to understand an already-challenging subject.
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.
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.
Finally, this makes the algorithm more complicated. From a pedagogical perspective, when the purpose is to teach algorithms, unnecessary complications are best avoided, as they just make it harder to understand an already-challenging subject.
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.
Context
StackExchange Computer Science Q#55905, answer score: 3
Revisions (0)
No revisions yet.