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.

Â