5
$\begingroup$

I'm a bit confused about stopping at Kth iteration on the Bellman-Ford algorithm to find the shortest path of at most length k from s to t. Let me show you a graph and explain you what I understand:

graph example

At first iteration, I will have:

  • Shortest path to get to A is S->A (cost 1)
  • Shortest path to get to B is S->B (cost 4)
  • Shortest path to get to T is still unknown

At second iteration I will have:

  • Shortest path to get to A is S->A (cost 1)
  • Shortest path to get to B is A->B (cost 2(A->B) + cost 1(S->A) = 3) updated!
  • Shortest path to get to T is B->T

But now going to B takes 2 edges instead of 1, so going to T is 3 edges away now: S->A->B->T, and this has happened in 2 iterations.

What am I understanding wrong?

Improve this question
$\endgroup$
3
  • $\begingroup$ the path to T doesn't get updated in the second iteration i.e after the second iteration the path to T still remains S->B->T remember second iteration can only use 1 intermediate vertex. It is the third iteration where the path to T gets updated as it can now use a budget of 2 vertices. try writing the code for the algorithm it helps. Also remember we fix a source vertex for the bellman ford as the problem is single source shortest paths so calculate the paths from S to every other vertex. $\endgroup$
    – Shubham Singh rawat
    Oct 24, 2016 at 2:35
  • $\begingroup$ @ShubhamSinghrawat But if I don't update B in the second iteration, then I won't be getting that I can reach B doing S->A->B with cost 6. So the parent of B must be A, the parent of A is S, and the parent of T is B. I've already coded the algorithm and this is the problem I'm facing. How can I store that the parent of B is S if I come from T, but it's A in any other case? $\endgroup$
    – Ivan
    Oct 24, 2016 at 9:33
  • $\begingroup$ I think what needs to "click" for you here is that $k$ iterations of BF only promises to discover the shortest paths to vertices for which the shortest path takes $k$ or fewer steps. T's shortest path takes 3 steps, so the algorithm doesn't make any promises about T after only 2 iterations. $\endgroup$
    – j_random_hacker
    Oct 24, 2016 at 13:08

2 Answers 2

Reset to default
2
$\begingroup$

The bellman ford algorithm presents to us the cost of all the shortest paths from a source vertex to all the other vertices . For constructing the path we reconstruct it after the algorithm has terminated and returned to us the cost. We backtrack on our solutions and reconstruct the path so don't get confused if you don't get the correct path at an intermediate step of the algorithm. (Just for some additional information while coding the algorithm you might have notices the use of an two dimensional array which stores solution at each step . the same is used to reconstruct the path.)

The recursive definition of the algorithm is

$\delta^{k+1}(v) = \min \Big(\delta^{k}(v), ~ \min_{x\in\mathbb{N} - \{v\}} (\delta^k(x) + w(x, v) ) \Big) $

For the example which you have presented

  • When the edge budget is $0$ :

The shortest path from S to T is $+\infty$.

  • When the edge Budget is $1$ :

we till have the cost to be $+\infty$.

  • When the edge budget gets $2$ :

We update the cost of our path to : $7$

  • When the edge budget is $3$:

We now get the following : $\min ( 7 , \min (6))$

Hence giving the final cost as $6$.

Improve this answer
$\endgroup$
1
$\begingroup$

In every iteration, all values are updated at once and they only use values from previous iteration. Imagine the program first calculating ALL of the new values before updating what is stored in memory (and therefore beginning to use these new values). In reality you probably have two arrays, one containing the previous iteration's result and the second one being filled in with the new values.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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