Lec 11 Belman Equation Part 2

namaskara we have been looking at the uh properties of uh the minimum weights of the shortest paths we are looking at the single Source shortest path problem from the source to other vertices we are interested in finding the shortest path towards that we are looking into the mathematical properties of the minimum weights or the weights of

the shortest Parts if G is an instance of the single Source shortest path problem and uh if Delta V is the weight of shortest path from s to V then we have derived the following equations when G has no negative Cycles when G has no negative Cycles we have proved that Delta s equal to zero

and Delta V equal to minimum over the edges all the incoming edges UV minimum over UV of Delta U plus weight of UV we can uh extend it and make it simpler looking by adding uh other conventions but uh in a sense this is the uh equation called bman equation and we have seen an example uh

where uh if G has zero cycle this equation allows us to have infinitely many Solutions and if G has a negative cycle of course these equations do not make any sense and as expected it doesn't have any solution we have also shown the non-existence okay to summarize here is the theorem let G equal to v e

WS B an instance of single Source shortest path problem if G has no negative cycle or zero Cycles then the equations x s = to0 x v equal to minimum over all the incoming edges u v over X U + weight of UV a small V

has a unique