1:02

Now, node v is certainly hoping not to have to inherit its

solution of plus infinity from the previous round, when i equals 0.

And indeed when i equals 1, the subproblem solution for

the vertex v is going to be 2.

That's because we can choose the last hop to be the edge s, comma v.

That has length 2, and

S's subproblem value last iteration when i equals 0, is 0.

By the same reasoning x's new subproblem value is going to be four,

because we can chose the last hop to be s, comma x, and add the cost of that

edge four to s's subproblem value, last iteration when i equals 0.

Now, the nodes w and t would love to throw out their plus infinity solutions and

get something finite.

And you might be thinking that because v and x now have finite distances,

those would propagate to the nodes w and t.

That will indeed happen, but we're going to have to wait until the next iteration,

we're going to have to wait until i equals 2.

The reason is if you look at the code, if you look at the recurrence,

when we compute the subproblem value at a given iteration i, we only make use

of the subproblem solutions from the previous iteration, i minus 1.

We do not use any of the updates that have already happened in the current

iteration i.

So because when i equals 0, a of 0 v, and a of 0 x were both plus infinity,

we're going to be stuck with a1w and a1t, both being plus infinity as well.

So, now let's move onto the next generation of the outer 4 loop,

when i equals 2.

The subproblem solution s is not going to change,

you're not going to do better than 0, so it's going to stay that way.

Similarly at the vertex v, you're not going to do better than 2, so

that's going to stay the same at this iteration.

Something interesting happens at the vertex x, however.

Now, in the recurrence you certainly have the option of inheriting

the previous solution.

So one option would be to set a of 2, comma x, to be equal to 4,

but there's actually a better choice.

So the recurrence is going to come out to be even smaller,

specifically if we choose that last hop to be the unit cost arc from vx.

We add that unit cost to v subproblem value, last iteration when i equals 1,

that was 2, 2 plus 1 equals 3.

So that's going to be the new subproblem value at x,

in this iteration where i equals 2.

So as advertised, the updates to the vertices v and

x in the iteration where i equals 1, now that i equals 2,

get propagated onto the vertices WNT.

So, WNT shed their plus infinity values, and

instead they pick up the values 4 and 8 respectively.

3:44

Notice that I've labeled the vertex t with an 8, not with a 7.

I've computed a of 2, comma t, to be 8.

And the reason is again the same updates from this iteration,

in particular the fact that x has dropped from 4 to 3

do not get reflected from other nodes in this same iteration.

We have to wait until the next iteration of the outer 4 loop before they happen.

So we're using the stale information at x,

that when i equals 1 its solution value is 4.

That's the information we're using to update t's solution value,

so it's 4 plus 4 or 8.

5:43

So answer A, quadratic and squared, what this is,

this is the number of subproblems, right?

So subproblems are indexed by a choice of i, which is somewhere between 0 and

n minus 1.

And a choice of a destination v, there's n choices for

each of those exactly n squared subproblems.

If we only ever spent constant time evaluating a subproblem,

then indeed the running time at Bellman-Ford would be big O of n squared.

And in most dynamic programming algorithms we've discussed in this class,

indeed you only spend constant time solving each subproblem.

The one exception being the optimal binary search trees problem,

where in general we spent linear time.

Here again, like optimal binary search trees,

we might spend more than constant time solving this subproblem.

The reason being, we have to do brute force search through a list of candidates

that might be super constant.

The reason is that each arc that comes in to the destination v provides

one candidate for what the correct solution to this subproblem might be.

So remember, the number of candidates, we had a quiz on this,

is proportional to the n degree of the vertex v.

And that can be as large as n minus one, linear the number of vertices.

6:58

Another interesting answer is C, that it's cubic in n, and D, the big O of n cubed

is a valid upper bound on the running time of the Bellman-Ford algorithm.

But it's not the sharpest possible upper bound, so why is it a valid upper bound,

as discussed just now is a quadratic n squared number of subproblems,

how much work do you do per subproblem?

Well, it's proportional to the n degree of a vertex,

the biggest n degree of a vertex is n minus 1, big O of n.

So, linear work for each of the quadratic number of subproblems resulting in cubic

running time.

7:30

There is, however, a tighter, a better analysis of the Bellman-Ford algorithm.

Now, why is O of mn bigger than n cubed?

Well what is m?

In a sparse graph, m is going to be theta of n,

and in a dense graph, m is going to be n squared.

So if it's a dense graph, it's true, big O of mn is no smaller than n cubed, but

if it's not a dense graph then this really is an improved upper bound.

8:31

But we know a much simpler expression for the sum of the n degrees.

This sum is simply equal to m, the number of edges.

In any directed graph,

the number of edges is exactly equal to the sum of the n degrees.

One easy way to see that is take your favorite directed graph and

imagine you plug the edges into the graph one at a time,

starting from the empty set of edges.

Well each time you plug in a new edge,

obviously the number of edges in the graph goes up by one.

And also, the n degree of exactly one vertex goes up by one,

whichever vertex happens to be the head of the edge that you just stuck in.

So therefore, the sum of the n degrees and the sum of the number of edges is always

the same, no matter what the directed graph is.

So that's why the total work is better than n cubed,

it's actually big O of m times n.

9:52

So in general, suppose that some iteration, earlier than the last one, so

say with a current index value of j, it just so happens that nothing changes.

That every destination v, you just reuse the optimal solution that you recomputed

in the previous iteration of the outer 4 loop.

Well then if you think about it, what's going to happen in the next iteration?

You're going to do exactly the same set of computations, with exactly the same

set of inputs, so you're going to get exactly the same set of results.

That is, it will be true again in the next iteration that you will just inherit

the optimal solutions from the previous one.

And that will keep happening over and over again until the rest of time.