0:00

Let's now proceed to the final algorithm for

Â the all-pairs shortest path problem that we're going to discuss.

Â It's called Johnson's algorithm, and the algorithm shows something pretty amazing.

Â It shows that even in graphs with negative edge lengths, the all-pairs shortest path

Â problem can effectively be reduced to just N indications of Dykstra's algorithm.

Â Even though Dykstra's algorithm needs non-negative edge links.

Â So, this video will discuss the key idea behind Johnson's algorithm,

Â will then proceed to the algorithm itself.

Â And this idea is a way of using vertex weights to re-weight shortest path links.

Â 0:50

The running time you get from this reduction is evidently

Â N times the running time of the single source sub routine.

Â And the running time of the sub routine is going to depend on whether your graph has

Â non negative edge lengths or not.

Â If you're in the lucky case where the graph has non-negative edge lengths

Â you get to use Dykstra's algorithm which runs blazingly fast almost linear time

Â M the number of edges times log N.

Â If you're dealing with a graph with the general edge lengths,

Â then the running time was not so good.

Â It would be N times the Bellming Ford running time which itself is N M.

Â 1:32

And now that we know about the [INAUDIBLE] algorithm which runs in big O of

Â N cubes time, there aren't a whole lot of reasons to care about this solution

Â in [INAUDIBLE] which runs Bellman-Ford end times except perhaps

Â the fundamentally distributed nature of that computation.

Â 1:47

Johnson's algorithm remarkably shows that the same running time we get here for

Â the non-negative edge limit case, N times N times log N, we can get equally well for

Â graphs that have general edge lengths.

Â 2:01

Specifically, Johnson's algorithm shows that the alt pair shortest

Â path problem in graphs with general edge lengths reduces to one indication

Â of the Bellman-Ford algorithm followed by an indication of Dexter's algorithm.

Â As we know, the Bellman-Ford algorithm runs in M times N time.

Â Any indications to Dexter's Algorithm is going to be N times M times Log N.

Â Putting it together we see that the N indications of Dexter Dominate

Â just barely.

Â So the overall running time we'll achieve is big O of N M log in.

Â Exactly the same running time we were getting for

Â the non-negative edge length of case.

Â 2:42

So this should probably sound a little too good to be true.

Â How on Earth can we reduce the shortest path problem with general edge lengths to

Â the special case where all the edge lengths are non-negative.

Â Indeed this is a trick that we actually thought some about in part one for

Â those of you who are alumni of that course.

Â Suppose you have the single short sorted path routes and

Â you've got a graph with some negative entries.

Â A very natural instinct is to say, well come on, that can't be that big a deal.

Â Let's just shift the edge a bit so they become non-negative.

Â And then keep your passed.

Â So if you have some graphs with the most edge link as minus five,

Â why not just add five to the link of every single edge.

Â Now you have a new graph, non-negative edge lengths, and

Â you just run Dijkstra's algorithm.

Â Big deal.

Â 3:24

So this quiz asked you to think about this edge shifting trick in general.

Â Suppose you have a graph and

Â there's a particular source S in destination T you're looking at.

Â And suppose you add some constant number,

Â capital M, to the length of every single edge of the graph.

Â Under what conditions will that preserve the shortest path between S and T.

Â 3:55

All right, so the correct answer is C Of the listed conditions,

Â the only one that guarantees that adding a constant M to every edge length

Â preserves the shortest path between a pair of vertices S and T is that all

Â of the paths between that pair of vertices have the same number of edges.

Â Maybe the easiest way to see this is just with a simple example.

Â 4:19

So consider this simple pic network where there's an S and a T and

Â there's two paths between them.

Â One with two hops each of cost one and one with one hop of cost three.

Â Now evidently in this graph the shortest

Â one is the one that goes threw the vertex V.

Â That one has length two the other one has length three.

Â Now suppose we add a fixed constant,

Â let's say the constant two to every one of these edges.

Â 4:43

In that case the two edges on top their lengths increase to three.

Â The edge on the bottom,

Â its length increases to five and you'll see that after we've shifted

Â all the edge lengths we've actually changed what the shortest path is.

Â It used to be the two hop path on top.

Â Now it's the one hop path on bottom that has length five.

Â The two hop path on top now has length six.

Â 5:05

So this shows that the answers A, B and D are all incorrect.

Â Why is C correct.

Â Well suppose it was the case that between the vertex S and

Â T every single path in the graph had exactly the number of edges.

Â Say every path had 12 edges.

Â Well then when you add a constant to every edges length, every path between S and T.

Â Their length goes up by exactly the same amount.

Â It goes up by 12 times M if each of the paths have 12 edges in it.

Â So if every single path between S and T goes up by exactly the same amount,

Â well then the shortest path remains exactly the same.

Â The ranking of the lengths of the various path that's exactly the same because we've

Â added exactly the same number to all of them.

Â So the broader point here is that if we want to find a transformation of

Â the lengths of a graph that reduces the general edge length case to

Â the non-negative edge length case,

Â we need to aspire toward transformations that preserve what shortest paths are.

Â And this transformation is not it.

Â 6:06

There's no reason for you to expect that there'd be any useful transformations

Â of this form, any shortest path preserving transformations that are nontrivial but

Â such transformations do exist.

Â That's the re-weighting technique, which we'll start exploring in the next quiz.

Â 6:31

Here is the twist.

Â For each vertex v there's going to be a number p

Â sub v associated with that vertex.

Â Don't worry about where these P sub V's come from we'll discuss that later.

Â Just think of it as any old number.

Â Could be seven, could be minus five.

Â Whatever, just one number per vertex.

Â 6:50

The key idea behind the reweighting technique is to use these end numbers

Â one weight per vertex, P sub V.

Â To use these end numbers to shift the edge lengths of the graph.

Â I'm going to use C prime to denote that these shifted or transformed edge lengths.

Â Here's the exact definition.

Â Consider an arbitrary edge E of this graph G.

Â Let's say the edge goes from the tail U to the head V.

Â The new length, C prime of E, is defined as the original length CE.

Â Plus the weights of these edges tail so plus P sub U,

Â minus the weight associated with these edges head that is minus P sub V.

Â 7:34

So, for example, consider an edge from U to V, that original length is two.

Â And let's say the weights associated with its tail and head are minus four and

Â minus three.

Â Remember, these vertex weights can be arbitrary numbers, positive or negative.

Â Well then, the shifted weight, C prime, is going to be,

Â by definition, two plus minus four.

Â Minus, minus three.

Â This of course is just equal to one.

Â 8:01

So that's the setup.

Â Here's the quiz question.

Â I want you to think about some fixed path, capital P.

Â Let's say it starts at a vertex S and ends at a vertex T.

Â Now capital P may or may not be the shortest path, I don't care.

Â It's just any old path starting at S, ending at T.

Â So suppose in the original network with the original edge length C sub E

Â the total length of this path P was capital L.

Â What is its new length L prime under these new edge lengths C prime.

Â 8:44

Under the new edge links C prime,

Â the path key's link does not in general remain the same but

Â it shifts by a predictable amount namely difference between the node

Â weight associated with S the origin of the path and T the destination of the path.

Â 9:17

So now we just expand each term in terms of its definitions so remember

Â the new edge length C prime of E is just the original length CE plus the weight

Â associated with the edges tail, U minus the weight associated with its head, V.

Â 9:33

Now consider a vertex other than S or T on this path,

Â some internal vertex on the path.

Â So such a vertex is going to be the tail of exactly one edge of P.

Â And it's going to be the head of exactly one edge of P.

Â So its vertex weight is going to show up with a coefficient of plus one once.

Â And that'll show up with the coefficient of minus one, one S,

Â obviously those two terms will cancel.

Â 9:54

So the only vertex weights that matter when we evaluate the sum is the weight of

Â the origin S and the weight of the destination, T.

Â The S only shows up once and it shows up as a tail so

Â it's vertex weight shows up with a plus one contribution.

Â So that's where the Ps term comes from.

Â Symmetrically the destination T only shows up once with a minus one coefficient.

Â so that's where the minus T comes from.

Â 10:16

So when the dust settles,

Â all that we're left with is the sum of the original edge links that we're using

Â the notation capital L for, plus this shift term, plus Ps of S, minus Ps of T.

Â 10:41

So what we've just learned about the reweighting technic.

Â Well, fix a graph and fix an origin vertex S and a destination vertex T.

Â What we just learned is that when you reweight using these vertex weights,

Â you shift every single ST path by exactly the same amount.

Â The length of every ST path, shortest or otherwise,

Â changes by exactly the quantity P of S minus P [INAUDIBLE] T.

Â 11:09

So this is now starting to sound pretty cool,

Â because let's remember our first quiz.

Â In our first quiz, we explored what happens when you just

Â add a fixed amount capital end to every edge of a graph.

Â We noticed it doesn't work in the sense that it can change the shortest path.

Â Why can it change the shortest path.

Â Well, different paths have a different number of edges.

Â So if you add some fixed amount to each edge,

Â you change different paths by different amounts.

Â That can screw up the shortest path.

Â If you're lucky and all of the paths between an S and a T have exactly the same

Â number of edges, then you shift them all by exactly the same amount and

Â you preserve the ordering of the paths.

Â But what do we see here.

Â We see that under no assumptions whatsoever about what the paths

Â between S and T like, Note reweighting shifts every single path

Â from ST by exactly the same quantity, the difference between PS and PT.

Â 11:57

Since reweighting changes the length of every path by exactly the same amount,

Â that means it preserves the shortest path.

Â Whatever was the shortest path previous is still the shortest path

Â after we've done re-weighting.

Â 12:12

So what.

Â Why is this interesting.

Â Well, let's dream big.

Â Suppose we could actually come up with vertex weights that

Â transformed the problem into one that we don't know how to solve blazingly fast.

Â Into one that we do know how to solve blazingly fast.

Â That is, what if we can find vertex weights that change an arbitrary instance,

Â that in general has negative edge lengths.

Â Into a shortest path problem, where all of the edge links are now non-negative.

Â 12:42

So if such a transformation existed, I hope that its use would be clear,

Â this would transform an instance of shortest path.

Â Where it seems like we're stuck with the Bellman-Ford algorithm because we start

Â with negative edge lengths.

Â And it transforms it into an easier one,

Â where we can apply Dijkstra's shortest path algorithm.

Â 13:00

Now, this best case scenario should sound like a free lunch to you.

Â Why do we think we can do basically a trivial amount of work.

Â Just the simple shift of the edge lengths.

Â And transform a seemingly harder problem, shortest path with general edge lengths,

Â into an easier one, shortest paths with non-negative edge lengths.

Â The catch, of course, is to figure out which vertex weights to use.

Â How do you know the magical edge weights that transform the general edge lengths

Â into the non-negative ones.

Â Actually, more fundamentally, why do we even think.

Â think that these vertex weights exist.

Â No matter how you pick the vertex weights, it's impossible to

Â transform all of the edge links so that they become non-negative.

Â Well, it turns out, as long as the graph has no negative cycle,

Â which we know as essential to computer shortest paths.

Â If there's no negative cycle,

Â there do always exist, magical choices of the vertex width P sub V.

Â That, transforms all of the edge links to B non negative.

Â Now it's not trivial to computer them, you have to do some work.

Â But it's not a prohibitive amount of work.

Â In fact, one indication of the Bellman Ford Algorithm, will be sufficient.

Â Johnson's algorithm puts those ideas together, that'll be the next video.

Â