Lec 15 Bellman Ford P2

namaskara we will continue our discussions on belman and for algorithm we have defined the class of walks w i okay the set of all walks from s to V with atmost I edges

Alpha I is the weight of the minimum walk Alpha i v is the weight of minimum walk in w i it's V it's depending on V so these Alpha I are satisfying certain interesting properties if G has no negative cycle if G has no negative cycle then Alpha i v equals minimum over U not equal to V of

alpha I -1 U plus weight of UV not only this we have alpha n -1 U = to Delta n -1 U which is equal to Delta U for all vertices this is true these two properties allow us to write the following program that would start from alpha 0 then in one iteration we will build alpha 1 for

all vertices and finally we stop at alpha n minus1 so here is the quote for this Bellman four this takes the directed graph v e weight function W Source S and G is G has no negative or zero cycle and we are going to use an array this is like a pseudo codee so we are

going to use an array this array is D array d i v is supposed to hold Alpha i v the purpose of this array D is to hold this value so we have to compute in our code the values D IV since our goal is to have Alpha IV the alpha IV based recurrence

is used for the computation of the D values okay so I initialize D 0 V to Alpha 0 V for all V so this is the first step in the first step d0 yes is zero and d0 V is infinity for all V belonging to V minus yes V minus the small s okay so you have