3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Raphael Apr 13 '16 at 8:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So one can compute shortest paths in O(E+V) using the algorithm I described for any graph, right? Then why is Dijkstra's algorithm even a big deal. Just ignore that algorithm and use Pinocchio's BF and re-write all algorithm textbooks. Or am I misunderstanding something? (I don't care about constant factors, only asymptotics) $\endgroup$ – Pinocchio Apr 13 '16 at 6:05
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 13 '16 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.