Let's now proceed to the final algorithm 
for the all pair shortest path problem, 
that we're going to discuss. 
It's called Johnson's algorithm, and the 
algorithm shows something pretty amazing. 
It shows that even in graphs with 
negative edge lengths, the all pair 
shortest path problem can effectively be 
reduced to just N indications of 
Dijkstra's algorithm. 
Even though Dijktsra's algorithm, for 
correctness, needs non negative edge 
lengths. 
So this video, we'll discuss the key 
idea, behind Johnson's algorithm. 
We'll then proceed to the algorithm 
itself, and this idea is a way of using 
vertex weights, to re-weight shortest 
path lengths. 
When we began our discussion of the all 
pair shortest path problem, we observed 
that the problem reduces to N indications 
of a suitable subroutine for the single 
source version of the problem. 
Simply by iterating over all N choices 
for the source vertex. 
The running time you get from this 
reduction is evidently N times the 
running time of the single source 
subroutine. 
And the running time of the subroutine is 
going to depend on whether your graph has 
non-negative edge links or not. 
If you're in the lucky case where the 
graph has non-negative edge links you get 
to use Dijkstra's algorithm which runs 
blazingly fast, almost linear time, M the 
number of edges times log N. 
If you're dealing with a graph with 
general edge links then the running time 
was not so good. 
It would be N times the Bellman-Ford 
running time which itself is M N. 
At the end of the day you get a running 
time of NM log N, for the non-negative 
edges case. 
Or N squared M for the general edge 
lengths case. 
And now that we know about the 
Floyd-Warshall algorithm which runs in 
big O of N cube times, there aren't a 
whole lot of reasons to care about this 
solution in general edge links that runs 
Bellman Ford N times. 
Except perhaps the fundamentally 
distributed nature of that computation. 
Johnson's out rhythm, remarkably shows 
that the same running time that we get 
here for the non-negative log-in case, M 
X N X log-in, we can get equally well for 
graphs that have general edge links. 
Specifically, Johnson's algorithm shows 
that the all pair shortest path problem 
in graphs with general edge lengths 
reduces to one invocation of the Bellman 
Ford algorithm followed by N invocations 
of Dijkstra's algorithm. 
As we know, the Bellman Ford algorithm 
runs in big O of N times N time. 
And indications to Dexter's algorithm is 
going to be N times M times log N. 
Putting it together we see that the end 
indications of Dijkstra's dominate just 
barely. 
So that the overall running time we 
achieve is big O of N M log N. 
Exactly the same running time we were 
getting for the non negative edge linked 
case. 
So this should probably sound a little 
too good to be true. 
How on earth can we reduce the shortest 
path problem with general edge lengths to 
the special case where all the edge 
lengths are non-negative? 
Indeed, this is a trick that we actually 
thought some about in part one, for those 
of you who are alumni of that course. 
Suppose you have the single source 
shortest path problem and you've got a 
graph with some negative edge lengths. 
A very natural instinct is to say, well, 
come on, that can't be that big a deal. 
Let's just shift the edge lengths so they 
become non-negative and then compute 
shortest paths. 
So if you have some graph where the most 
negative edge length is minus five, why 
not just add five. 
To the length of every single edge. 
Now you have a new graph, non-negative 
edge links, and you just run Dijkstra's 
algorithm, big deal. 
So this quiz asks you to think about this 
edge shifting trick in general. 
Suppose you have a graph and there's a 
particular source S in destination T 
you're looking at. 
And suppose you add some constant number. 
Capital M to the length of every single 
edge of the graph. 
Under what conditions will that preserve 
the shortest path between S and T? 
All right, so the correct answer is C. 
Of the listed conditions the only one 
that guarantees that adding a constant M 
to every edge length preserves the 
shortest path between a pair of vertices 
S and T is that all of the paths between 
that pair of vertices have the same 
number of edges. 
Maybe the easiest way to see this is just 
with a simple example. 
So consider this simple pink network, 
where there's an S and a T and there's 
two paths between them. 
One with two hops, each of cost one, one 
with one hop of cost three. 
Now, evidently in this graph, the 
shortest path is the one that goes to the 
vertex V. 
That has length two, the other one has 
length three. 
Now suppose we add a fixed constant, 
let's say the constant two to every one 
of these edges. 
In that case the two edges on top, their 
links increased to three. 
The edge on the bottom, it's link 
increases to five and you'll see that 
after we've shifted all of the edge 
lengths, we've actually changed what the 
shortest path is. 
It used to be the two hop path on top. 
Now it's the one hop path, hop path on 
the bottom. 
That has a length of five. 
The two hop path on top now has length 
six. 
So this shows that the answers a, b and d 
are all incorrect. 
Why is c correct? 
Well suppose it was the case that. 
Between the vertex S and T, every single 
path in the graph had exactly the same 
number of edges. 
Say, every path had twelve edges. 
Well, then when you add a constant to 
every edge's length, every path between S 
and T, their length goes up by exactly 
the same amount. 
It goes up by twelve times M if each of 
the paths have twelve edges in it. 
So if every single path between S and T 
goes up by exactly the same amount, well, 
then the shortest path remains exactly 
the same. 
The ranking of the lengths of the various 
paths is exactly the same because we've 
added exactly the same number to all of 
them. 
So the broader point here is that if we 
want to find the transformation of the 
lengths of a graph that reduces the 
general edge length case to the 
non-negative edge length case we need to 
aspire toward transformations that 
preserve what shortest paths are. 
And this transformation is not it. 
There's no reason for you to expect that 
there'd be any useful transformations of 
this form. 
Any shortest path preserving 
transformations that are non-trivial but 
such transformations do exist. 
That's the re-weighting technique which 
we'll start exploring in the next quiz. 
So in this quiz, were again going to 
think about one of our usually directed 
graphs. 
Every edge has a link and the links can 
be arbitrary real numbers. 
Here is the twist: For each vertex V, 
there's going to be a number, piece of V, 
associated with that vertex. 
Don't worry about where these piece of 
V's come from, we'll discuss that later. 
Just think of it as any old number; could 
be seven, could be -five, whatever; just 
one number per vertex. 
The key idea behind the re-weighting 
technique is to use these end numbers, 
one weight per vertex, p sub v, to use 
these end numbers to shift the edge 
lengths of the graph. 
I'm going to use c prime to denote these 
shifted or transformed edge lengths. 
Here's the exact definition: consider an 
arbitrary edge, e, of the, of this graph, 
g. 
Let's say the edge goes from the tail, u, 
to the head, v. 
The new length c prime of e is defined as 
the original length, ce, plus the 
weights. 
Of this edges tail, so plus P sub U, 
minus the weight associated with this 
edges head, that is minus P sub B. 
So for example, consider an edge from U 
to V that original length is two, and 
let's say the weights associated with its 
tail and head are minus four and minus 
three. 
Remember these vertex weights can be 
arbitrary numbers, positive or negative. 
Well then, the shifted weight C prime is 
going to be by definition two plus minus 
four minus, minus three. 
This of course is just equal to one. 
So that's the set up, here's the quiz 
question. 
I want you to think about some fixed 
path, capital P, let's say it starts at a 
vertex S and it ends at a vertex T. 
Now capital P may or may not be the 
shortest path. 
I don't care. 
Just any old path, starting at S, ending 
at T. 
So suppose, in the original network with 
the original edge links C's to B, the 
total length of this path P was capital 
L. 
What is its new link, L prime, under 
these new edge links, C prime. 
So the correct answer is C. 
Under the new edge lengths C prime the 
path P's length does not in general 
remain the same but it shifts by a 
predictable amount. 
Namely, the difference between the node 
weights associated with S, the origin of 
the path and T, the destination of the 
path. 
This follows by a simple calculation. 
So the new length of the path P is of 
course just the sum over the modified 
edge lengths, the sum over the C primes 
of the edges in P. 
So now we just expand each term in terms 
of it's definitions, or remember the new 
edge length C prime of E is just the 
original length C E, plus the weight 
associated with the edges tail. 
U minus the weight associated with it's 
head V. 
Now consider a vertex other than S or T 
on this path some internal vertex on the 
path, so such a vertex is going to be the 
tail of exactly one edge of P and it's 
going to be the head of exactly one edge 
of P. 
So its vertex weight is going to show up 
with a coefficient of plus one, once and 
it'll show up with a coefficient of minus 
one once. 
Obviously those two terms will cancel. 
So the only vertex weights that matter, 
when we evaluate the sum, is the weight 
of the origin s, and the weight of the 
destination t. 
The s only shows up once, and it shows up 
as a tail, so its vertex weight shows up 
with a +one contribution. 
So that's where the p sub s term comes 
from. 
Symmetrically the destination t only 
shows up once with a -one coefficient, so 
that's where the -t comes from. 
So, when the dust settles, although we're 
left with the sum of the original edge 
links that we're using imitation capital 
L for, plus this shift term, plus piece 
of S minus piece of T. 
Alright so now that we've slogged through 
the algebra let me explain to you why we 
went through that exercise. 
What is the potential application of this 
reweighting technique? 
So what did we just learn about the 
rewaiting technique? 
Well fix a graph and fix a origin vertex 
s and a destination vertex t. 
What we just learned is that when you 
rewait, using these vertex waits. 
You shift every single s, t path by 
exactly the same amount. 
The length of every s, t path, shortest 
or otherwise. 
Changes by exactly the quantity p of s 
minus piece of t. 
So this is now starting to sound pretty 
cool, cause let's remember our first 
quiz. 
In our first quiz, we explored what 
happens when you just add a fixed amount 
capital M to every edge of the graph. 
We notice it doesn't work, in the sense 
that it can change the shortest path, why 
can it change the shortest path? 
Well different paths have a different 
number of edges so if you add some fixed 
amount to each edge you change different 
paths by different amounts, that can 
screw up the shortest path. 
If you're lucky and all of the paths 
between and S and a T have exactly the 
same number of edges, then you shift them 
all by exactly the same amount and you 
preserve the ordering of the paths. 
But what do we see here? 
We see that under no assumptions 
whatsoever about what the paths between S 
and T like, node reweighting shifts. 
Every single path from S to T by exactly 
the same quantity, the difference between 
PS and PT. 
Well since reweighting, changing the 
length of every path by exactly the same 
amount, that means it preserves the 
shortest path. 
Whatever was the shortest path 
previously, is the shortest path after 
we've done reweighting. 
So what, why is this interesting? 
Well lets, cream big. 
Suppose we could actually come up, with 
vertex weights, that, transform the 
problem, into one that we don't know how 
to solve blazingly fast, into one that we 
do know how to solve blazingly fast. 
That is, what if we can find the vertex 
weights that change, an arbitrary 
instance, that in general has, negative 
edge lengths, into, a shortest path 
problem where all of the edge lengths are 
now, non negative. 
So if such a transformation existed, I 
hope that it's use would be clear. 
This would transform an instance of 
shortest paths, where it seems like we're 
stuck with the Bellman-Ford 
algorithm'cause we start with negative 
edge lengths. 
And it transforms it into an easier one 
where can we can apply Dijkstra's 
shortest path algorithm. 
Now this best case scenario should sound 
like a free lunch to you. 
Why do we think we can do basically a 
trivial amount of work, just a simple 
shift of the edge lengths and transform a 
seemingly harder problem, shortest paths 
with general edge lengths, into an easier 
one? 
Shortest paths with non-negative 
influence. 
The catch, of course, is to figure out 
which vertex weights to use. 
How do you know the magical edge weights 
that transform the general edge lengths 
into the non-negative ones? 
Actually, more fundamentally, why do we 
even think that these vertex weights 
exist? 
Maybe no matter how you pick the vertex 
weights, it's impossible to transform all 
of the edge lengths. 
So. 
That they become non negative. 
Well it turns out, as long as the graph 
has no negative cycle, which we know is 
essential to compute shortest paths. 
If there is no negative cycle there do 
always exist magical choices of the 
vertex weights P sub V that. 
Transforms all of the edge links to B 
non-negative. 
Now it's not trivial to compute them, you 
have to do some work. 
But, it's not a prohibitive amount of 
work. 
In fact. 
One invocation of the Bellman Ford 
algorithm will be sufficient. 
Johnson's algorithm puts those ideas 
together. 
That'll be the next video.