Lec 10 Belman Equation Part 1

Namaskara, in the previous session, we have seen the mathematical properties that would relate the shortest path distances in an equation called bellman equation. Let G = (V, E, w, s) and delta v is weight of the shortest path from s to v. We have formed the following bellman equations when G has no negative cycle. We assume that G

has no negative cycles. The bellman equations are given by, we define a variable, x v is a variable associated with vertex v belong to V. and we form the following equation: x of s is equal to 0 and x of v is equal minimum over u not equal to v of x of u plus weight of u v.

This is for all vertices v other than s, okay. so, these are called bellman equations, we can form the bellman equation and then attempt to solve them. so, let us see an example to understand the subtleties and issues involved in dealing with bellman's equation. consider the following graph, here is an example to explain the ideas and concepts behind the

bellman's equation; the computations to be done with bellman equations. consider the graph s, a, b, c; it is a directed graph and we have the edges like this. These are all the edges. First I will give the following weight 1, 2, 3, 4, 5 and 6. These are the weights of the edges.

For example, weight of the edge cs is 4. so this is a weighted graph, s is the source vertex. so I can write down the bellman equation. In bellman equation you will have for each edge uv playing a role for the variable xv. xv for any vertex v is minimum of uv into xu plus weight of uv. so,

for each incoming edge there will be a term. so, for each incoming edge there will be a term. so, for the vertex v if the in-degree is 10, there will be 10 terms and you have to take the minimum of those 10 terms. Okay. so, number of terms here is same as in-degree of v,