HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Shortest path between 2 vertices using at most K edges using Bellman-Ford

Submitted by: @import:stackexchange-cs··
0
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:

  • 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

  • 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.