0:21

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.

1:48

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.

3:02

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.

4:53

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.

5:49

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.

6:21

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.

9:32

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.