Lec 13 Belman Equation Part 4

so this is a decreasing sequence on numbers and uh this can go up to minus infinity however whatever is the graph whether it has a negative cycle or positive cycle it really doesn't matter what kind of graph it is the Delta sequence is always finite Delta 0 V is greater than or equal to Delta 1 V is

greater than or equal to Delta n minus1 v and it stops here and after that all values are equal that is because as we have seen already the maximum number of edges in any path is just n minus one that is the reason why this will not extend any further you will have uh only equal values it won't

descend Beyond this point so we write like this equal to Delta n v = to Delta n + 1 V and so on for all of them it is equal how are alpha values and Delta values are related our goal is the Delta values so we will see how alphas and Deltas are

related since every path is a walk since every path is a walk it's clear that p k v is a subset of uh w k v a path that has got at most K edges is also a walk that has got at most K edges therefore every element of PK is an element of WK WK may have more elements

so because of this uh the bigger uh uh sets uh will have smaller uh minimum value right therefore uh Alpha uh k v is less than or equal to Delta k v all right so Alpha and Delta are related this way there's another interesting fact is always greater if G has no negative

cycle then Alpha k v is equal to Delta k v that is because if a Gra has no negative cycle every shortest walk will indeed be a shortest walk path if G has no negative Cycles every and also we will well we will avoid zero cycle in the sense zero cycle it just can be simply removed