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.