Let's now proceed to
the final algorithm for the all-pairs 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-pairs shortest path problem can effectively be reduced to just
N indications of Dykstra's algorithm. Even though Dykstra's algorithm
needs non-negative edge links. So, this video will discuss the key
idea behind Johnson's algorithm, will then proceed to the algorithm itself. And this idea is a way of using vertex
weights to re-weight shortest path links. When we began our discussion on the all
pairs shortest path problem we observed that the problem reduces to end
indications of a suitable sub routine 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 sub routine. And the running time of the sub routine is
going to depend on whether your graph has non negative edge lengths or not. If you're in the lucky case where
the graph has non-negative edge lengths you get to use Dykstra'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 the general edge lengths, then the running time was not so good. It would be N times the Bellming Ford
running time which itself is N M. At the end of the day you get
a running time of N M log N for the non-negative edges case, or
N squared m for the general edges case. And now that we know about the [INAUDIBLE]
algorithm which runs in big O of N cubes time, there aren't a whole lot
of reasons to care about this solution in [INAUDIBLE] which runs
Bellman-Ford end times except perhaps the fundamentally distributed
nature of that computation. Johnson's algorithm remarkably shows that
the same running time we get here for the non-negative edge limit case, N times
N times log N, we can get equally well for graphs that have general edge lengths. Specifically, Johnson's algorithm
shows that the alt pair shortest path problem in graphs with general
edge lengths reduces to one indication of the Bellman-Ford algorithm followed
by an indication of Dexter's algorithm. As we know, the Bellman-Ford
algorithm runs in M times N time. Any indications to Dexter's Algorithm
is going to be N times M times Log N. Putting it together we see that
the N indications of Dexter Dominate just barely. So the overall running time we'll
achieve is big O of N M log in. Exactly the same running
time we were getting for the non-negative edge length of 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
short sorted path routes and you've got a graph with
some negative entries. A very natural instinct is to say, well
come on, that can't be that big a deal. Let's just shift the edge a bit so
they become non-negative. And then keep your passed. So if you have some graphs with
the most edge link as minus five, why not just add five to
the link of every single edge. Now you have a new graph,
non-negative edge lengths, and you just run Dijkstra's algorithm. Big deal. So this quiz asked 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 pic network
where there's an S and a T and there's two paths between them. One with two hops each of cost one and
one with one hop of cost three. Now evidently in this graph the shortest one is the one that goes
threw the vertex V. That one 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 lengths increase to three. The edge on the bottom, its length increases to five and
you'll see that after we've shifted all 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 on
bottom that has length 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 number of edges. Say every path had 12 edges. Well then when you add a constant to every
edges length, every path between S and T. Their length goes up by
exactly the same amount. It goes up by 12 times M if each
of the paths have 12 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
path that's 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 a 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 nontrivial but such transformations do exist. That's the re-weighting technique, which
we'll start exploring in the next quiz. So in this quiz we're getting you to think
about one of our usual directed graphs. Every edge has a length and
the lengths can be arbitrary real numbers. Here is the twist. For each vertex v there's
going to be a number p sub v associated with that vertex. Don't worry about where these P sub V's
come from we'll discuss that later. Just think of it as any old number. Could be seven, could be minus five. Whatever, just one number per vertex. The key idea behind the reweighting
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 that
these shifted or transformed edge lengths. Here's the exact definition. Consider an arbitrary
edge E 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 these edges tail so
plus P sub U, minus the weight associated with these
edges head that is minus P sub V. 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 setup. 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
ends at a vertex T. Now capital P may or may not be
the shortest path, I don't care. It's just any old path starting at S,
ending at T. So suppose in the original network
with the original edge length C sub E the total length of this
path P was capital L. What is its new length L prime under
these new edge lengths C prime. So the correct answer is C. Under the new edge links C prime, the path key's link does not
in general remain the same but it shifts by a predictable amount
namely difference between the node weight associated with S the origin of the
path and T the destination of the path. This follows by a simple calculation. To 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 its definitions so remember the new edge length C prime of E is just
the original length CE plus the weight associated with the edges tail, U minus
the weight associated with its 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 that'll show up with
the coefficient of minus one, one S, 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 it's vertex weight shows up
with a plus one contribution. So that's where the Ps term comes from. Symmetrically the destination T only shows
up once with a minus one coefficient. so that's where the minus T comes from. So when the dust settles, all that we're left with is the sum of
the original edge links that we're using the notation capital L for, plus this
shift term, plus Ps of S, minus Ps of T. All right, 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 technic. So what we've just learned
about the reweighting technic. Well, fix a graph and fix an origin
vertex S and a destination vertex T. What we just learned is that when you
reweight using these vertex weights, you shift every single ST path
by exactly the same amount. The length of every ST path,
shortest or otherwise, changes by exactly the quantity
P of S minus P [INAUDIBLE] T. So this is now starting
to sound pretty cool, because let's remember our first quiz. In our first quiz,
we explored what happens when you just add a fixed amount capital
end to every edge of a graph. We noticed 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 an 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,
Note reweighting shifts every single path from ST by exactly the same quantity,
the difference between PS and PT. Since reweighting changes the length of
every path by exactly the same amount, that means it preserves the shortest path. Whatever was the shortest path
previous is still the shortest path after we've done re-weighting. So what. Why is this interesting. Well, let's dream big. Suppose we could actually come
up with vertex weights that transformed 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 vertex
weights that change an arbitrary instance, that in general has negative edge lengths. Into a shortest path problem, where all
of the edge links are now non-negative. So if such a transformation existed,
I hope that its use would be clear, this would transform
an instance of shortest path. Where it seems like we're stuck with the
Bellman-Ford algorithm because we start with negative edge lengths. And it transforms it into an easier one, where 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 the simple shift of the edge lengths. And transform a seemingly harder problem,
shortest path with general edge lengths, into an easier one, shortest paths
with non-negative edge lengths. 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. think that these vertex weights exist. No matter how you pick the vertex weights,
it's impossible to transform all of the edge links so
that they become non-negative. Well, it turns out, as long as
the graph has no negative cycle, which we know as essential
to computer shortest paths. If there's no negative cycle, there do always exist, magical
choices of the vertex width P sub V. That, transforms all of the edge
links to B non negative. Now it's not trivial to computer them,
you have to do some work. But it's not a prohibitive amount of work. In fact, one indication of the Bellman
Ford Algorithm, will be sufficient. Johnson's algorithm puts those ideas
together, that'll be the next video.