0:00

We're now well positioned to state Johnson's algorithm in its full

Â generality. The input as usual is a directed graph G.

Â Each edge has a edge length C sub E, it could be positive or negative.

Â The input graph G may or may not have a negative cost cycle.

Â As usual, when we talk about solving a shortest path problem we mean that if

Â there is no negative cost cycle, then we have no excuse. So we better correctly

Â compute all of the desired shortest paths.

Â In this case between all pairs of vertices.

Â If there is a negative cost cycle, we're off the hook.

Â We don't have to compute shortest paths, but we.

Â need to correctly report that the graph does indeed have a negative cost cycle.

Â Step one is the same hack that we used in the example.

Â We want to make sure that there's a vertex from which we can reach everybody

Â else. So let's just add a new one that by

Â construction has that properties. So we add one new vertex to little s, we

Â add N new edges. One from s to each of the original

Â vertices and each of those new N edges has length zero.

Â We're going to call this new, bigger graph g prime.

Â The second step, just like in the example, is to run a shortest path

Â computation using this new vertex S as the source.

Â Since the graph G in general has negative etch cost, we have to resort to the

Â Belmont Ford out rhythm to execute the shortest path computation.

Â Recall that the Bellman-Ford Algorithm will do one of two things.

Â Either it will correctly compute the shortest path distances that we're after,

Â from the source vertex S to everybody else, or it will correctly report.

Â That the graph it was fed, namely g prime, contains [SOUND] a negative cost

Â cycle. Now, if g prime contains a negative cost

Â cycle, that cycle has to be the original graph, g.

Â Our, the new vertex, s, that we added, has no incoming arcs at all, so it

Â certainly can't be on any cycle, [SOUND] so any negative cycle is the

Â responsibility of the original graph, G. [SOUND] Therefore if Bellman-Ford finds

Â us a negative cost cycle, we're free to just halt and correctly report that same

Â result. So from here on out, we can safely assume

Â that G and G prime have no negative cost cycle, and therefore that the

Â Bellman-Ford algorithm did indeed correctly compute shortest path distances

Â from S to everybody else. As in the example, we are going to use

Â these shortest path distances, [SOUND] all of which are finite by construction.

Â As our vertex weights, our P sub Vs. We then form the new edges lengths, the C

Â primes, in the usual way. C prime of an edge E going from U to V is

Â the original length CE plus the weight of the tail P sub U minus the weight of the

Â head P sub V. In the example, we saw that the new edge

Â length C prime are all non-negative. We will shortly prove that, that property

Â holds in general. If you define your vertex weights in

Â terms of shortest path distances from the new vertex S to everybody else in this

Â augmented graph G Prime it is always the case that your new edge lengths would be

Â non-negative. Assuming that for now, it makes sense to

Â use Dijkstar's algorithm N times, once for each choice vertex to compute all

Â pairs shortest paths in the graph G with the new edge length C prime.

Â In a particular iteration of this four loop.

Â Say, when we're using the vertex u as the source vertex.

Â We're going to be computing n of the shortest path distances that we care

Â about. From u to the various n possible

Â destinations. And let's call those shortest paths

Â computed by Dijkstra in this iteration d prime of u, v.

Â 3:28

So perhaps you're thinking that at this point we're done.

Â Right? We transformed the edge links using

Â re-weighting to make them non-negative and as we know once things are not

Â negative end Dijjkstra and you're good to go.

Â But there's one final piece of bookkeeping that we have to keep track

Â of. So, the shortest path distances that we

Â compute in step four, these D primes, these are the shortest path distances

Â with respect to the modified costs, the C primes.

Â And what we're responsible for outputting the shortest path distances with respect

Â to the original links, the C's. But fortunately there's a very easy way

Â to extract the true shortest path distances from.

Â The D primes from the shortest path distances relative to the modified costs.

Â We know that D primes are wrong, there computed with respect to the wrong costs.

Â But we know exactly what they're off by. So D primes are off by exactly P sub U

Â minus P sub V amount. So to go from the D primes back to

Â shortest path distances that we really care about, we just need to subtract that

Â term back off, and that's step five. [SOUND] That completes the description of

Â Johnson's Algorithm which, in effect, is a reduction from the all pairs shortest

Â path problem with general edge lengths to N plus one instances of the single source

Â version of the problem, only one of which has general edge lengths, N of which have

Â only non-negative edge lengths. [SOUND] Analyzing the running time of

Â Johnson's algorithm is straight forward. Let's just look at the work done in each

Â of the five steps. In step one, we just add one new vertex

Â and n new edges, so that takes o of n time to accomplish.

Â 6:06

So why is this running time so cool? Well two reasons.

Â The first reason is that for sparse graphs this solution blows away the

Â previous algorithms that we had that could handle negative edge lengths.

Â The two previous solutions that we knew, that you could use with graphs with

Â negative edge lengths were either run Bellam Ford N times or used the

Â Floyd-Warshall. And in sparse graphs where M is big O of

Â N, both of those solutions run in cubic time or in cubed time.

Â This solution for sparse graphs, when M is O of N is of, of N squared Times a log

Â N factor, so it's way better than either using Bellman-Ford N times or using

Â Floyd-Warshall. The second reason this running time is so

Â cool is that it matches the running time we were getting already in the special

Â case when edge links were non negative. so this is very different than how we

Â were conditioned to think about the world when we talked about single source

Â shortage path problems. Remember, in those problems, we have Dexter's

Â algorithm which only handles non negative edge links but runs in near linear time

Â and there's no algorithm known for single source shortest paths that's near linear

Â that can handle negative edge links, the Bellman Ford algorithm certainly is not

Â near linear running time. That's Big O of N times N.

Â Johnson's Algorithm shows that while negative edge lengths are indeed an

Â issue, they can be handled in one shot using just one invocation of

Â Bellman-Ford. While the Bellman-Ford algorithm is

Â indeed quite a bit slower than Dijkstra's algorithm, it's only roughly a factor of

Â N slower. So one invocation of Bellman-Ford doesn't

Â change the overall running time when we already have to do N invocations of

Â Dijkstra's algorithm, even in the special case of the problem where all of the edge

Â lengths are non-negative. So that is why for all pairs shortest

Â paths we see a convergence in the performance of algorithms that solve the

Â problem in general, and algorithms that only solve the problem in the special

Â case of non-negative edge lengths. The missing piece to the correctness

Â argument is understanding why in general the modified edge links, the C prime E's

Â are guaranteed to be non-negative. We saw that they were non-negative in

Â this specific example, but we have not yet proved it in general.

Â We'll do that on the next slot. Assuming for the moment that, that is

Â true, that the modified edge links are indeed non-negative, and therefore, when

Â we invoke Dijkstra it will correctly compute shortest paths, we're pretty much

Â done. In particular, recall that we had a quiz

Â in the previous video where we analyzed the ramifications of re-weighting.

Â And we saw that if you re-weight using particular vertex weights, some P sub Vs.

Â 8:34

Then, for a given choice of an origin u, and a given choice of a destination v.

Â Every single uv path has its length changed by exactly the same amount, by a

Â common amount. Namely, the difference between u as

Â vertex weight p sub u. And the destination v as vertex weight, p

Â sub v. So that means, when we invoke Dijkstra's

Â algorithm in step four. Indeed, gets the shortest paths correct.

Â The shortest path distances are incorrect.

Â But we know exactly how much they're off by.

Â They're off by Pu minus P sub v. And that is corrected for in step five.

Â So that's why assuming correctness of Dykstra's algorithm Which in turn relies

Â on non negativity of the modified edge links.

Â The end result of Johnson's algorithm is indeed the correct shortest path

Â distances. To finish the analysis of Johnson's

Â algorithm all that remains is to prove the following claim.

Â Which is that for every single edge of the graph, it's length after we do re

Â weighting is non negative. So the proof in fact is not hard.

Â It follows quite easily from properties of shortest path distances.

Â So fix your favorite edge E, let's say going from U to V.

Â The vertex weights are, by construction, just shortest path distances from the

Â vertex little s. Well remember S is the extra source

Â vertex that we added to the original input graph G.

Â 10:38

The length of this path which goes from S to V is of course just the length

Â incurred going from S to U, Which is just P sub U, plus the length of the final hop

Â which is just the length of this edge, C sub U V.

Â Now this is just some old path from S to V.

Â The shortest path from S to V, can of course, only be shorter.

Â And only piece of V, the vertex way to V, is by definition, the length of the

Â shortest path from S to V. And now, we're good to go because the

Â modified length of this edge C. That is C prime sub E is just the

Â difference between the right hand side of this inequality and the left hand side.

Â So that's why the difference is guaranteed to be non negative.

Â Since this was an arbitrary edge it holds for all the edges.

Â That completes the proof in the analysis of Johnson's algorithm.

Â