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.