So we've talked a bit about various running time optimizations of the basic Bellman-Ford algorithm. Now let's talk about optimizing the space required by the algorithm. To orient ourselves, lets just think about how much space is needed by the basic algorithm we've been studying thus far. All right, so the correct answer here is the first one, A. The space required by the basic Bellman-Ford algorithm is quadratic in the number of vertices. It is theta of n^2. Why? Well, the space is dominated by the 2D array that we fill in, and there is only a constant amount of space per sub-problem, and there is n-squared sub-problems. Number one index is the budget on how many edges we are allowed to use, 'I' ranges from 0 to n - 1 and then the other index is just a destination and there's n of those. So in this video, we will talk about how you can do better, how you can get away with linear space, not quadratic space. The initial observation is a simple one. Let's just return to the formula that we used to populate all of the entries of the array. So, we always take the, a bunch of a whole bunch of candidates, what are the candidates? Well either we can inherit the solution from last iteration ia, i - 1v or we can choose something to be the last hop wv and then we just paste together the best solution 2w from last iteration. So ai - 1w plus we pay for the last hop, the length of the edge wv. But here's the point, staring at this formula, which subproblem values do we care about? Well not that many of them and in particular the trait shared by all of the interesting candidates are they're all from the last iteration the first index and everything on the right hand side is always i - 1. As a consequence, as soon as we finished one batch of sub-problems for some value of i, we've computed aiv for all v, we can throw out the results of all of the previous rounds of sub-problems. Ai - 1, Ai - 2, and so on. All we need is the freshest batch, the most recent iteration, to correctly proceed. If we do that, the only sub problems we're keeping track of are the ones that we're filling in, in the current round i and we're remember the solutions from the previous round i - 1, that means at any given moment in time we're only keeping track of big o of n different sub problems. And this linear space bound is even more impressive than it might appear at first, and that's because if you think about the responsibility of our algorithm in this problem, we have to output a linear number of things, right? We're not just outputting one number. We're outputting n numbers, shortest path distance from s to every possible destination. So the space is really constant per statistic that we have to compute. One thing I'm not going to discuss explicitly but I think it would be a good exercise for you. Go back to all of the other dynamic programming algorithms we discussed, and of course by now there are many, and see which ones you can do a comparable optimization. Which sub-problems do you need to keep around to compute the new ones? And if you throw out all the ones that you're not going to need anymore, what does that reduce the space to? For many of the problems we've just studied, you're going to see a big improvement in the space required. But this would be a good time to pause and stop for a few seconds and think about possible negative consequences of this space optimization. So suppose we do this, either in the context of shortest path going forward, or some other dynamic programming algorithm. We throw out the values of old sub-problem solutions that we seemingly don't need any more to push the recurrence further. Are there any drawbacks to this space optimization? [SOUND] So the answer depends. [SOUND] If all you care about is the value of an optimal solution and not the optimal solution itself, then you may as well just throw out all of these old sub-problems and you don't need anymore to push the recurrence further. It's not going to hurt you at all. If, however, you want the optimal solution itself, and not just its value. Well, how did we actually accomplish that in the past? We had these reconstruction algorithms. How do the reconstruction algorithms work? You took the entire filled in table and you traced backward through it. At each entry of the filled in table you looked at which of the candidates won, which comparison came out the winner when you filled in this entry, that told you a piece of what the optimal solution has to look like and then you go backward through the table and repeat the process. If you've thrown out most of your filled in table. How are you going to run this reconstruction algorithm? In the context of the Bellman-Ford algorithm, how are you going to reconstruct shortest paths if you haven't remembered all of the sub-problems of all of the previous iterations. And you can then certainly imagine in a routing application for example, you don't just want to know that the shortest path has length seventeen, you want to know, what route should we take to get from point A to point B? So in the rest of this video, I'm going to describe a solution for the Bellman-Ford algorithm. I'm going to show you how we can retain the constant space per vertex guarantee while recovering the ability to reconstruct shortest paths. So, the idea is, for a given value of i and a given destination v, we're going to keep track of, not just the one piece of information, the length of the shortest path from s to v that uses the most I edges, but also a second piece of information, [SOUND] which is the second-to-last vertex on such a path. So it's still going to be just constant space per sub-problem. So we're going to call this second two-dimensional array b. We're going to call its entries predecessor pointers. Again, the semantics are this pointer points to the predecessor of this destination v on a shortest path from s to v that has the most i edges. Of course, if i is sufficiently small there may be no such paths from s to v, and in that case we just have a null predecessor pointer. So for a moment let's just forget about the space optimization that we're trying to attain and let's just observe that if we correctly computed these capital B's then simply traversing predecessor pointers would reconstruct shortest paths. So, why is this true? Well, two reasons. Reasons that you've seen explain other things as well. So, the first reason is remember that we're assuming that the input graph has no, no negative cost cycle. Therefore shortest paths have a most n - one edges. Therefore the bn - 1v is actually store in them the final hop of a shortest path period, with no edge budget from s to v. So in the bn - 1v is the final batch of predators or points, if we correctly compute them, they are telling us the last hop on a shortest path to v. Now, the other part of the correctness comes from the optimal substructure limbo. So, remember way back when we started talking about shortest paths and their optimal substructure, we said, well if only we had a little birdy which told us what the last hop of a shortest path was, then the shortest path would just be that last hop concatinated with a shortest path from s up to the penultimate vertex w and, these predecessor pointers are exactly this little birdy. We're storing at v what the last hop is, w, v and so, we know that it's just that last hop with the shortest path back to S from W. And by traversing, that's exactly what you do, you just reconstruct the rest of the path apart from s to w. So, if we correctly compute predecessor pointers then they enable the simple reconstruction of shortest path, just by traversal after the fact. So, that leaves of with the task of correctly computing these predecessor pointers. It's not hard. I think many of you could just fill in the details yourself, but let me just give quick rundown. So remember in general we have this 2-D array capital B, it's indexed by the edge budget I and it's indexed by the destination v and we're supposed to fill in biv with a final hop on a shortest path from s to v that uses at most I edges and if no such paths exist then it's just null. For the base case that's when I equals zero and here everybody's predecessor pointer is null. So the way we're going to fill in the entry biv is going to depend on which of the candidates won in the competition to be the shortest path for aiv. In essence this predecessor pointer biv is just caching the results of the competition we ran to find the shortest path for aiv. So to make this precise, let's just recall the formula that we used to compute for aiv, given the solutions to the last batch of sub-problems. Case one is when you inherit the solution from the last round ai minus 1v. In addition each possible choice for a last hop w, v furnishes another candidate for the optimal solution of this round in which your going to pay, you're going to pay the optimal solution to the sub problem i minus 1w plus the length of the edge wv. So we're going to fill in the biv array. Basically, just to reflect what happens when we computed the solution to AIV. In essence, what we're doing in the 2D, 2D array b is remembering the most recent vertex w that's responsible for furnishing a new shortest path from s to v. So in case one the boring case where at iteration I we just inherit the solution from the last round of course in the b entry we just inherit the last hop of the previous round. That is if we use case one to fill in aiv then we just sent biv to be, bi - 1b. So the interesting case is when aiv is filled in using case two of the formula, that is when this shortest path from s to v suddenly improves, given a budget of I-hops, as opposed to just, I-1hops. In that case we're just going to cash the results of the brute force search that we did to evaluate the formula. That is we justt remember the choice of the pan ultimate vertex W, that achieved the minimum in this round. Now notice that, just like the formula that we used to populate the capital a array. The original array. To compute these BIVs, all we need to know is information from the last round. Information from the round i - 1. So just like with the a array, we can throw out all of the predecessor pointers that date back before yesterday. Before the previous round. Therefore, we again, need only constant space per destination v. To maintain both the shortest path distance from s to v with the most i-hops. And the predecessor pointer. So this is great. For input graphs that don't have negative cost cycles, we can not nearly compute the shortest paths in constant space per destination. We can also compute the predecessor pointers in that same space which allows the reconstruction of shortest paths. So one other thing you might want is to handle graphs that do have negative cost cycles. Now in a separate video we showed that just checking whether an input graph has a negative cost cycle or not is easily addressed by a simple extension of the Bellman-Ford Algorithm. You tack on one extra iteration of the outer for loop. You let I range not just up to n - 1 but all the way up to n. And if you see for some destination v, an improvement in the extra iteration when i = n, then that guarantees that there is a negative cost cycle, that is if and only if. But, in the same way you might want to actually have the shortest paths not really their value, you might want to actually have a negative cost cycle and not really know that one exists. It turns out you can solve the reconstruction problem for negative cost cycles as well, using the Bellman-Ford algorithm and predecessor pointers in exactly the way we've been maintaining them here. I'm not going to talk through all of the details of the solution. I'll leave it to you as a somewhat nontrivial exercise to think through how this really works, but the gist is as follows, so you run the Bellman-Ford algorithm, you maintain the predecessor pointers as on this slide, and if the input graph does have a negative cost cycle, then at some iteration, you will see a cycle amongst the predecessor pointers. Furthermore, that cycle of predecessor pointers must be a negative cost cycle of the original input graph. This means that detecting a negative cost cycle if one exists reduces to checking for a cycle in the predecessor pointers which of course you can solve using depth for a search at every iteration.