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.