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.