Thus far we've seen how in input graphs 
without negative cost cycles, the 
Bellman-Ford algorithm correctly computes 
shortest paths from the source vertex S 
to all destinations V. 
But what about input graphs that do have 
negative cost cycles? 
In this short video we'll see how to 
extend the Bellman-Ford algorithm leaving 
its running time essentially unchanged, 
so that it can easily check whether or 
not the input graph has a negative cost 
cycle. 
So the following claim is going to 
indicate the appropriate extension of the 
Bellman-Ford algorithm. 
In particular this claim characterizes 
the presence or absence of a negative 
cost cycle in the input graph. 
In terms of behavior in the Bellman-Ford 
algorithm. 
Okay, well actually, the Bellman-Ford 
algorithm if, we ran it for one extra 
iteration. 
So currently, we stop the bellman ford 
itera algorithm when the outer index I is 
equal to N minus one. 
For the claim we're going to envision 
running that outer four loop for one 
extra iteration, when I equals N running 
the same over-currents for all of the 
destinations V. 
[SOUND] So the insertion then is that G 
the input graph has no negative cycle, if 
and only if we don't get any new 
information from this extra batch of 
sub-problems. 
That is if and only if, A and V is 
exactly the same thing as A and -1V for 
every possible destination V. 
Equivalently the input graph does have a 
negative cost cycle if and only if there 
exists some sub-problem. 
There exists some destination V, where we 
see an improvement at V buy running the 
government Ford out rhythm for this extra 
iteration. 
So we're approved the claim in the next 
slide, it's not too hard. 
But I hope it's immediately clear what 
the implications of the claim are. 
How we check for a negative cost cycle. 
So now, given a arbitrary input graph 
with no promises, it might have a 
negative cost cycle, it might not. 
What do you do? 
You run Bellman-Ford but you run it for 
one more iteration. 
You run it for the outer four loop Index 
I going all the up to N. 
And, you check does some sub-problem 
value change in that final iteration or 
not. 
If not, if all of your A and -1V's are 
the same as you A and V's, then, by the 
claim you know that there's no negative 
cost cycle. 
By our previous work. 
We know the Bellmanu2013Ford algorithm is 
correct. 
So, we happily return the A and minus one 
V'S as the correct shortest path 
distances as before. 
If on the other hand you notice there's 
vertex V so, that A and V is different is 
smaller than A and minus 1V, then you 
say, hey. 
There's a negative cycle by the claim, so 
I'm not going to give the shortest path 
distance for you, that wouldn't make 
sense. 
There is negative path cycle and you 
punt. 
And of course this one extra iteration of 
the Bellman-Ford algorithm has a 
negligible effect on its running time, 
it's still Big O of N times N. 
So I'm lying a little bit in this claim. 
There's an edge case I'm not handling 
properly. 
When I wrote down the claim I was 
thinking about arguably the common case 
of input graphs G where there exists a 
path from S to every other destination V. 
That is, input graphs where all of the 
shortest path distances are finite. 
So if that's not the case then the claim 
as stated is not correct. 
one way to see that would be just to 
generate, to generate instance where the 
source vertex S has no outgoing arcs at 
all and maybe the rest of the vertices 
form a negative cost cycle. 
And that kind of graph. 
The left hand side of this claim is false 
but right hand side of this claim is 
satisfied. 
So to modify it for graphs that may have 
infinite distances, I'm just going to 
modify the left had side to say G has a 
negative cost cycle that is reachable 
from the source for text S. 
There are if you actually wanted to 
detect in the input graph whether there 
was a negative cycle at all reachable 
from s or otherwise there are various 
tricks you can do to solve that again 
using the duman ford algorithm. 
So for example given an input graph you 
can add a dummy sort of fictitious extra 
vertex and add arcs from that vertex to 
everybody else with link zero run them 
before on that graph and that will detect 
a negative graph cycle if one exists. 
So now that we know why we want the claim 
to be true, let's understand why it is 
true. 
Let's go to the proof. 
So the claim asserts something that's if, 
and only if. 
On the left-hand side is the property of 
the input graph having no negative cost 
cycle. 
On the right-hand side is the property 
that the Bellman-Ford algorithm does not 
make any changes if you, run one extra 
iteration. 
So proofs like this have two parts. 
Assuming the left, prove the right. 
Assuming the right, prove the left. 
One of these two parts, if you think 
about it, we already did, when we proved 
that the Bellman-Ford algorithm is 
correct. 
Four graphs with no negative cost cycles. 
That is, if the left-hand side holds. 
If the input graph doesn't have a 
negative cost cycle. 
We already argued that you don't have to 
run the outer four loop beyond I Equals N 
minus one that is sufficient to capture 
the shortest path so in particular take I 
as big as you like for example I equals N 
your not going to see even shorter paths 
your going to get exactly the same sub 
problem solutions. 
The content, then, is the reverse 
direction. 
So let's assume that we run Bellman-Ford 
an extra iteration, and none of the 
sub-problem solutions change. 
Now I warned you there is this edge case 
when the input graph doesn't have a path 
from s to all other verticies and you 
have infinite distances I'll leave those 
details to you so lets just focus on the 
case when there is a path from s to 
everything else and in particular the sub 
problem of values are going to be finite. 
So a little notation. 
I'm going to use lowercase D of a vertex 
V to denote the common value of its 
sub-problems in the final two iterations, 
when I equals N minus one and when I 
equals N. 
So now the plan is we're just going to 
stare at the formula that we used to 
evaluate these sub problems. 
It's right there staring at us from the 
pseudo code for the Bellman Ford 
algorithm. 
From that we will get an inequality 
relating these D values to each other. 
And from that inequality we will be 
easily able to deduce that every cycle of 
the input graph is indeed non negative. 
That's the left hand side of the 
statement. 
[SOUND] So what formula did we use to 
fill in this extra iteration of the 
table, the A N Vs? 
Well we just took the better of, on the 
one hand, A N minus one V, the solution 
from the previous iteration, and then 
also the best of the candidates that use 
c last hop W V and concatenate a path of 
the most N minus one edges to W along 
with that edge W V. 
[SOUND] Let's also note that with our new 
notations these little d values the 
common value of a sub problem in the n 
minus one and f iterations you can write 
the left hand side of this formula is d 
of v and in the case two sub problems we 
can write a and minus one w as d of w. 
Now because the left hand side of this 
equation is a minimum over a bunch of 
candidates on the right hand side if we 
instantiate if we zoom in on any one 
candidate on the right hand side so any 
choice of this last hop wv we get 
something which is at least as big as the 
left hand side again the left hand side 
is the smallest of all of the candidates. 
So in particular for a given choice of 
the last hop w comma v we get that d of v 
is at most d of w plus the length of the 
edge of w to v. 
Really all this inequality is saying is 
that one way to get a path from S to V is 
to take a path from S to W in 
concatenates the final hop W, V, the 
shortest path to V can only be better 
than this one particular candidate that 
goes via W. 
Now, remember what it is we're trying to 
prove. 
We're trying to prove that the input 
graph has no negative cost cycles. 
So, let's just pick our favorite cycle, 
capital c and show that it has non 
negative cost. 
This is going to be in a sneaky 
application of the inequality that we 
just wrote down in pink specifically we 
are going to sum that inequality over all 
of the edges in the cycle. 
its going to be clear if I just 
rearranged that pink inequality a little 
bit. 
So, now let's look at the, some of the 
edge links in the cycle capital so you 
remember this is what we want to prove as 
non-negative. 
So, we sum over the edges w coma v in big 
c and for each edge, we look at its cost, 
little c of w v. 
By the pink inequality, we can lower 
bound this by a sum over the edges in the 
cycle capital C of the difference between 
the d values of that edge, the endpoints 
of the edge. 
Notice that for a given arc wv on the 
cycle the tail of this arc w its d value 
appears with a coefficient of plus one 
and the devalue of the head of this arc v 
appears with a coefficient of minus one. 
But cycles, of course, have the very 
special property that every vertex of the 
cycle appears exactly once as the tail of 
some arc and exactly once as the head of 
some arc. 
So each D value of a vertex on a cycle is 
going to appear once with plus one 
coefficient and once with minus one 
coefficient. 
So when we get massive cancellation, 
we're left with just zero. 
So, the cycle capital c has non negative 
costs. 
That was an arbitrary cycle. 
So it's true simultaneously of all of the 
cycles in the input graph. 
That's exactly what we were trying to 
prove. 
So again, the presence of negative cost 
cycles in an input graph is characterized 
by the behavior of Bellman Ford in an 
extra iteration. 
That's why it's easy to extend the basic 
algorithm. 
To check negative cycles without 
affecting the running time.