What is the shortest path problem? So we're given a graph, G that is we're given. A vertex and an edge set. A set of nodes and a set of links. And it is a weighted graph so each link has a certain number a weight associated with it, interpretable as the cost of using that link. And it is a directed graph so node I goes to node j doesn't mean that node j also goes to node i. And our job is actually very simple. We just want to find a minimum cost path, so there might be multiple. We just need to find one, between each pair of source and destination. Okay? So that's a very simple statement and it turns out this is one of the most extensively studied graph theoretic optimization problems. It's got the name, the shortest path, which is a little misnomer, because the best name really should be minimum. Cross path problem. Of course if the cost is the physical distance, then a special case is shortest distance, and if the path of linked cost is actually all one for every link, then this is basically a minimum hot count. Path problem. So how can we solve this problem? There's so many different nice ways. We will look at a specific one based on the dynamic programing principle. Or the so called Bellman Equation. And if you are taking an optimization course you probably will spend quite a few lectures on dynamic programing. Okay? But here we just illustrate it in one specific algorithm. Again, notice that we're given the graph G. And for each link there is a cost, the CIJ for link I to J. And the main idea behind this Bowman's equation and the resulting Bowman-Ford's algorithm was the following: if you are node i. And you have a destination n. You want to figure out the best way to get there, the shortest path or main course path. Well, you have to get there from one of your outgoing neighbors. There should be an arrow here. Say you got three neighbors, so whatever path you take, you have to first start with one of the three neighbors. Okay, and there's a cause of going to the neighbors, CIK here. Then, let's denote by p sub it. As the minimum cost it takes for node I, to go to destination N, from I to N. Let's assume this N is a common fixed N for everyone. Okay. So we just suppress the N notation here, with implicit understanding that we talk about this nation being node N. So this is the minimum cost for source I that goes to source N, using T or less halves. You think but here we usually reserve that index for time and indeed we can view this as the iteration index over discreet times loss as well. Both have a temporal meaning over a duration as well as a spatial physical meaning here. So we're using that notation, we can write down the following obvious statement. For example, at time zero, every nose takes infinite cause cuz you cannot get to the destination using zero or less hops, okay. Unless node I is node n itself, you are the destination yourself, then in that trivial case, yeah you are, already there. And we can also write down, therefore at whatever time or whatever number of halves you may need, you can always get to yourself, with a zero cost. Okay. So these are just obvious statements using this definition of the notation PIT. Now here comes the somewhat magical part. We want to find out PI, let's say using T plus one or fewer halves. That means we have to go through, well, one of the outgoing neighbors indexed by k, okay, with the cost CIK. Once you get to that neighbor, one of these neighbors, you've already used up one hop. So you need to get to that destination with T hops or fewer. And if you could know, still if at this point, the minimum cost it takes for node K, that's the neighbor you just picked to go to, to get to destination N using T or fewer hops, then that's great'cause you can then add these two up. Now, the question is, which outgoing neighbor K to pick? Well, I'm going to pick whichever one can give me the smallest sum . So, pick the min of the sum over all the nodes indexed by k, that's your outgoing neighbors This is the famous Bellman's equation. And we can, indeed, rigorously prove that if this equality holds. Now, this boundless equation is useful for an algorithm only if you can actually efficiently compute a pkt. Then you can compute PIT plus one. But can you compute PKT efficiently? Well, Let's use the idea of recursion. So using recursively this Bellman's equation you can like keep riding this from T plus one to T, to T minus one, T minus two, all the way down to zero. Then you see that no nodes can get to destination in zero of fewer hops except that destination is cell. And then you can recursively work your way back up, back to T plus one. We're going to illustrate this whole process and example numerically in a minute. This is the famous. Bellman-ford algorithm. Okay. Essentially, it is an algorithm for efficient computation following this Bellman's equation. Notice the min is taking over only those nodes K that are your outgoing neighbors. So, this is one of those beautiful, elegant and yet extremely useful and so often used equations, like those we encountered in lectures one, two, and three, back there. So, without going into the underlying dynamic programming principles, because then we'll be dragging sort of off the track a little bit. Let's take a look at an example to illustrate how this can be computed, at least centrally. Okay, suppose you actually know the whole graph. How can you compute this essentially? Then we'll look at, in the next module of the video, the distributed version where no one has a global bird's eye view of the whole graph. Then how can you implement this computation? But. So here is the centralized example. This is an extremely small graph. For such a small graph, you can probably just eyeball the answers. Please don't eyeball the answer. Let's follow the Bellman's equation cuz the purpose is not to redefine the shortest path in this graph. Who cares is to illustrate the Bellman-Ford algorithm. Okay? So, notice in this graph, we got A, B, C, D, four nodes, five nodes. There is also a common destination node N. We can do All to one routing basically, Okay? Find out all the shortest path for these four nodes to a common destination N. We could also do one to all following a similar procedure, Okay? So, You look at these link ways which are numbers written next to the directed weight links in the graph. You see hey, they are some negative numbers. What do you mean by negative weights? The three negative numbers, was really for generality sake. It may have some physical meaning in some context but for this purpose we just want to show that is okay to have negative weights on a link for Bellman-Frod to still work out. As long as you don't have, No negatively weighted cycles. Cycle is a path connect concatenation of links that ends up where it started. Okay? So for example, C to A to B to C, that's a cycle, right? Is a concatenation of links, of three links, and then you end up where you started with. And the total cycle path is minus two plus eight plus four which gives you ten as the cycle went, which is positive number so as long as we don't have a cycle with total negative wave and s'okay, what's wrong with a negative weighted cycle? Well because if this whole cycle is negative weighted then, you can just keep going looping this infinite number of times and it will push your total cost down to infinite. Before you take, you know, one more hop to get to the destination, or two more hops. So, no negative cycles, otherwise the problem is ill-defined. Negative weighted links, that is okay. Alright. So, let's run the Bellman's equation now. At time T for this graph, just remember the graph now, okay. We have the following. Pa in time one, okay, this is T equals one. My Bellman's equation is the min of the cost from A to B, and then the min cost from B to the common destination N suppressed in the notation from the previous iteration or using one fewer hop, that's means use zero hopes okay or through neighbor, C or go through neighbor D. What are these three numbers? Well it's eight plus infinity, six plus infinity and four plus infinity because the previous iteration they're all infinity and this is infinity which means you have no way to get from node A to the destination in the first iteration i.e. Using one or fewer hops. Which is obviously true, it's trivial. Of course A is separated from N by two nodes by one nodes so you at least need two hops to get to N. But again, don't eyeball solution. We just want to illustrate a Bellman equation using a simple a numeric example as possible. Similarly, you can write down PB. At this time iteration is also implemented. What about PC? Actually PC is not infinity any more cuz is the mean of three numbers, six plus zero if you go through node N directly. Minus five plus infinity if you goes to its outgoing neighbor B. And minus two plus infinity if you go through its outgoing neighbor A. But clearly you want to pick the first one that's six. And PD, similarly can find to be seven. So it's infinity , infinity six and seven and iteration one, okay? Using one or fewer hops. Now, let, iteration two starts. You can now see suddenly, that PA at two is not infinity anymore. It is the mean out of three choices of its outgoing neighbor. Through B, you get A+ infinity, because it's still infinity in the last iteration. Pb at iteration one is to infinity, so it's ainfinity. Plus infinity. That's no good but then you've got sixCs. Plus Cs. No Cs minimum cost last iteration, using one of your halves. That is six, Very good. Now you've got four plus seven if you go through D. Now clearly the mean of that is eleven, four plus seven go through neighbor D. You should write on a separate sheet of paper what exactly node are you using? Okay this is purely computing the shortest path. But obviously you can also trace back the actual path itself. In addition to the cost of the shortest path. Good so PA is now eleven. Following similar calculation PB now is three and PC now is two. You can easy derive this yourself or see it in the textbook. What about PD? We're going to start writing PD cuz PD is boring. D had only one outgoing neighbor which turns out to be the destination itself. So it will always stay the same number which is seven, okay. So now it becomes eleven, three, two, seven. Keep going. Iteration three, you see that PB, Iteration three is now the min of what? Eight plus what? What does it take to node B to get to the destination three? Okay, very good. A plus three, Okay? Six2, plus two. Four7. Plus seven. Notice the last iterations updates into eleven, three, two are reflected here. Now, you've got three and two, okay? So now, this is seven and similarly PB iteration is -one. Oh, I'm sorry, not seven this is eight. -One MPC is two . Okay. Pd again, remains the same. Keep going, t equals four. Okay? Pa now is , you can compute, 7pb is minus one pc is two, pd is still the same. And how about we keep going, t equals five, equals six and so on. Turns out we don't need to do that. There are two ways to look at it. One is it no longer changes. Okay? You can try it but you will see that it no longer changes It converged the Bellman-Ford algorithm at the right answer. And second You, if you actually had a bird's eye view and know how many nodes there are, you know there are four nodes. Okay. Other than yourself out there. So, you got to be able to stop at iteration four. You know this APRE, because if you keep on going any further. I say, well I give you one more half, you can go up to five halves or more or, or, or fewer. You can go up to a 100 halves of your, not just four halves of your. Say I don't care, it doesn't help me any more. Why? Because the only way for me to leverage beyond four halves. Is to actually go through the same node twice.'Cause there are only four other nodes out there. And therefore, I will have to go through a cycle. But I know cycles are not negatively weighted, so it will add to my cost. No cycles needed, so I don't need to go beyond, four hops or more. Either way, you know, you can stop. And this illustrates the Bellman-Ford algorithm. But it does not show you how to do it distributively.