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.