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.