patternMinor
Shortest path between 2 vertices using at most K edges using Bellman-Ford
Viewed 0 times
pathbellmanedgesshortestbetweenfordusingverticesmost
Problem
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:
At first iteration, I will have:
At second iteration I will have:
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?
Let me show you a graph and explain you what I understand:
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?
Solution
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
The shortest path from S to T is $+\infty$.
we till have the cost to be $+\infty$.
We update the cost of our path to : $7$
We now get the following : $\min ( 7 , \min (6))$
Hence giving the final cost as $6$.
(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$.
Context
StackExchange Computer Science Q#65019, answer score: 2
Revisions (0)
No revisions yet.