Belmen ford algo

#1

how we are sure that after n-1 steps all vertices will set to lost optimal distance…??

#2

hello @shampblocks
if we have n nodes.
then shortest path between any two nodes can be at max of length n-1 right?

and that is why we are running only n-1 steps

#3

How it is dynammic programming?? How to think like other problem we think?? Like recurrence relation type?? Top down dp??

#4

the idea is first we are finding shortest past with at most 1 length.
then we are finding shorted path with atmost 2 length
…
then we are finding shortest path with atmost k length.

now to find k lenght shortest path we are taking help of k-1 length shortest path( just add 1 edge to k-1 lenght shortest path to get k lenght shortest path) and that is why we put this under dp category.

#5

How to think it like recursive way top down??

#6

Please clear the doubt

#7

@shampblocks
i think i have already explained this

recurrence relation should be
dp(i,j,k)= min(dp(i,j,k-1) , edge weight ( i…c) + dp(c,j,k-1) )

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.