0:00

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.

Â 4:59

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.

Â 6:14

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.

Â 8:39

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.

Â 10:40

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.

Â 11:35

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.

Â