In this video we'll cover Johnson's very cool algorithm.
It shows how to use the re-weighting technique we introduced in the last video
to reduce the all pair shortest path problem in graphs that can have negative
edge lengths to a single invocation of the Bellman-Ford shortest path algorithm
followed by N invocations of Dijkstra's shortest path algorithm.
We concluded last video daydreaming about this best case scenario, where we have a
graph with negative edge links. But somehow we come up with these magical
vertex weights that transforms all of the edge links to be non negative.
And it turns out that the magical vertex weights which will realize this best case
scenario are best computed by a shortest past algorithm.
So before describing Johnson's algorithm in general let me just walk you through
some of the steps in an example. So I've drawn a directed graph with six
vertices and seven edges. I've annotated each edge with its cost in
blue. Notice that some of the edges do indeed
have negative costs so it is not currently an option to run Dijkstra's
algorithm on this graph. There is no negative cycle however in
this graph, it only has one cycle, the directed triangle at the top and it's
overall cost is one. So we could run the Bellman Ford
Algorithm, on this graph if we wanted. So our strategy is to compute a magical
set of vertex weights so that when we transform the edge lengths using the
re-weighting technique described in the previous video we wind up with a graph
that now has only non-negative edge lengths.
So where do these vertex weights come from?
Well, the great idea in Johnson's algorithm is to compute them using a
subroutine for the single-source, shortest path problem.
To implement this, we need a well defined instance of the single source shortest
path problem. In particular, we need a source vertex.
So that's a pretty good idea. There's only one small problem with it,
which is that when you pick your arbitrary source vertex it might not be
able to reach all of the other vertices. And to get our magical vertex weights,
we're really going to want finite shortest path distances from our
arbitrary source to everybody else. For example, in the graph that I've drawn
here on the slide, it doesn't matter which of the six vertices you choose as
your source vertex. You will not be able to reach all of the
other five. So how do we get around this issue?
Well, with a simple hack. We're just going to add a new vertex, so
a seventh vertex in this example. And we're going to connect this new
vertex, which I'm just going to call S, to all of the original vertices with a
direct arc of length zero. We are then going to compute shortest
paths from this new artificial source vertex S to all of the vertices from the
original graph. Notice that by construction that we're
going to get the finite shortest path distance from S to all of the vertices
we've installed a direct path from S to everybody else.
Notice that because this new vertex S has no edges going into it, it's effectively
invisible from the perspective of all of the original vertices in the graph G.
So in particular, the shortest path distance between any pair of vertices U
and V in the original graph is unchanged by this addition of the vertex S.
Similarly, whether or not G has a negative cycle, it's unaffected by the
addition of the vertex S. The next step of Johnson's Algorithm is
to invoke a single source shortest path algorithm using this newly added vertex S
as our source vertex. Now in this example, and in general,
we're thinking about the case of negative edge lengths.
So we're not going to be able to use Dijkstra's algorithm to solve this single
source version of the problem. We're going to have to use the Bellman
Ford algorithm to do this computation. So let's now go ahead and figure out what
are the shortest path distances from S to the other six vertices in this graph on
the slide. So let's start with a vertex A.
What's the shortest path distance from S to A?
Well, it's certainly no worse than zero. There's a path directly from S to A of
length zero. And indeed in general all six of the
shortest path distances that we compute will be zero or less.
So the question, is there a path from S to A that is negative, that's better than
zero? Well what are the options?
We could go from s to c at length zero but then we'd pay four to get back to a.
So that has length four, so that's no good.
A little bit better but still not good enough would be to zip straight from s to
b that has length zero, from b to c, now we're up to, now we're down to - one.
But then we have to go from c to a and so we add four.
So we get three. So we conclude that the shortest path
from s to a is indeed the direct one hop path of length zero.
Most of the other vertices are more interesting however.
Think for example about vertex B. We could of course zip straight from S to
B along the path of link zero. But we can get shorter than that.
If we go first from S to A at link zero, and then from A to B, then that path has
combined length minus two. And that is in fact the shortest path
distance from S to B. The shortest path distance to C is just
to take that same shortest path to B and then concatenate the edge of cost minus
one form B to C. That is the shortest path from S to T
goes S to A to B to C for a combined length of zero plus minus two plus minus
one, minus three in all. So now let's move to the bottom of the
graph, the vertex Z is pretty easy to think about.
There's only one path in the entire graph, that's the direct one from S to Z,
so Z's just going to have trivial shortest path distance of zero.
So now, for the vertex, y, you got a bunch of different options.
You could, of course, go straight from s to y with zero, but there's a lot of
things better than that. You can also go from s to z, and then,
along the minus four arc to y, that would give you a path of length minus four, but
you can do even better than that by going first to a, then to b, then to c, and
then to y. So that gives you a path whose edge costs
are zero, minus two, minus one, and minus three.
That gives you a combined total of minus six, the shortest path distance to y.
Generally the shortest path to get to X, the best thing to do is to accumulate of
all of the negative weight at the top of the graph, go via vertex C.
And it's true you have to pay the cost two to get from C to X.
You still wind up with an end length of minus one, which out performs the direct
zero length path from X to S. Now, the brilliant insight in Johnson's
Algorithm is that this shortest path computation is extremely useful.
In fact, these computed shortest path distances are exactly the magical vertex
weight, weights that we're seeking. They're going to transform all of the
edge links from general to non-negative. So let's define the weight P sub V of a
vertex V from the original graph, that is one of the six vertices in this example
that we started with, as the shortest path distance we just computed from the
extra vertex S to that vertex V. What I want to do next is see the effect
of reweighting using these vertex weights.
So to do that, let me redraw the example. So let's recall the formula for the
re-weighting technique given vertex weights like these.
You define the new length C prime E of an edge E say from U to V as its original
length CE plus the length of its tail P sub U minus the weight of it's head, P
sub V. So let's just do this computation for
each of the seven edges. Let's start at the top.
Edge A comma B. So we start with its original length:
minus two. We add the weight of the tail, so we're
adding zero. And then we subtract the weight of the
head, so we're subtracting minus two. That is, we're adding two.
So we get minus two plus two or zero for the new length C prime B for the edge A
comma B. Similarly for the edge B, C, we take the
original length -one, we add to it -two, and then we subtract -three but as we add
three, then again it all cancels out, we get zero for the new cost of arc B, C.
For the arc C comma A we take the original length four, we add minus three,
we subtract zero. So the arc C comma A has a strictly
positive shifted length that's now one. If we look at the arc C, X we take the
original link two. We add -three and we subtract -one.
So that again all cancels out and C, X has a new cost of zero.
Same thing happens with the arc C, Y. We start with minus three, we add another
minus three, we subtract minus six, that gives us zero.
For the arc Z comma Y, we start with one, we add zero, we subtract minus one so we
get a new cost of two on the arc Z comma X.
Finally for the arc Z comma Y, we start with minus four, we add zero, we subtract
minus six, that is, we add six, so that gives us a new length of two.
So I don't expect you to have intuition or semantics for the computations that we
just did; but, at least in this example the proof is in the pudding.
We just used these shortest path distances as weights and re-weighting
magically made all seven edges have non-negative edge lengths, they all have
length either zero, one or two. So what we've now done, at lest in this
example is realize the best case scenario we were dreaming about.
Remember what the key point of the rewaiting technique video was, we pointed
out that reweighting preserves shortest paths.
If you have some vertex waits, some P sub Vs, you change all the edge lengths by
reweighting. For every origin S and every destination
T you shift the length of every S, T path by exactly the same amount.
By P sub S minus P sub T, the difference between the vertex weights at the origin
and the destination. So by changing all paths by exactly the
same. Same amount you preserve which path is
the shortest. So that's a cute party trick.
It's not really clear or useful. But we're hoping that maybe by
reweighting, in the shortest path preserving way, could allow us to
transform the general edge links version of a shortest path problem, to the non
negative edge links version of the problem.
So that we're not stuck with the slower Bellman Ford algorithm, and instead we
get to use the faster Dice Dijkstra's algorithm.
And that's now exactly what we can get away with here, at least in this example.
We did the transformation, the new graph has only non negative edge links.
Now we can just run Dijkstra's algorithm once for each choice of the source vertex
to compute all of the shortest path distances.