Transcript
Welcome everybody to our lecture 14 of 6006. This is our last lecture on graph algorithms. In particular, the last lecture we'll have on weighted shortest paths. Uh but we're going to talk about a slightly different problem today. Uh different than single source shortest paths, we're going to be talking about all pairs shortest paths. Okay, but first let's review our single source shortest paths algorithms. We had BFS, DAG relaxation, Dijkstra, which we saw last time, which you know, gets pretty close to linear. Right? V log V + E is pretty close to linear. It's much closer to linear than the general algorithm algorithm we have for solving single source shortest paths, namely Bellman-Ford, which is a little bit more like quadratic.
This is like the difference between for sparse graphs, this is like the difference between sorting using insertion sort in n squared and merge sort in n log n, for example, right? We're going to get a actually quite a big bonus for large input sizes by using Dijkstra when we can. Okay? Today, we're going to be focusing on this new problem called all pairs shortest paths. It's not really complicated. Instead of having a single source, we are essentially wanting to give in an input. This is our weighted graph. Where we've got a a graph VE and we've got a weight function from the edges to the integers.
Right? This is our general weighted graph. We want our output to be something like the shortest path distance from U to V for every U and V in our vertex set. Right? That's what we want to return. Now, there's one caveat here that if if there's a negative weight cycle in our graph, in other words, if any of these delta UVs is minus infinity, there's a negative weight cycle in our graph. So, unless uh I guess or abort if uh G contains a negative weight cycle. Okay? So, we're not actually going to worry about negative weight cycles in today's class. If we have a graph, it could have negative weights, right?
These are any integers, could include negative weight edges. But as long as all of our path distances are, you know, bounded from below, none of them are negative infinity, we don't have any negative weight cycles, then I want you to output all of these shortest path distances. Now, in particular, this output could any of these outputs needs to have size theta of V squared. Right? Because for every pair of vertices, I need to return to you a number or infinity or minus infinity or something like that. But we are not dealing with the case with minus infinity. The output could have size the this is a theta here.
It does have size V squared. Right? Uh but in particular, it's at least V squared. Because I need to give a number for each pair of vertices. And so, we couldn't hope for linear time in the size of this graph for this problem, right? Single source shortest paths for certain versions of the problem, we need to read the graph, and so we need to use linear time. But in this problem, our output has quadratic size in the number of vertices. So, in a sense, we can't do better than this. Right? We can't do better than quadratic. And it actually what's one way we could solve all pairs shortest paths by using stuff we've already done in this class?
That's why I put this slide up here, right? Yeah, we could just solve a single source shortest paths algorithm from every vertex in my graph. You know, that's seems like a stupid thing to do, right? It's almost brute force on the vertices, but it's certainly a way we could solve this problem in polynomial time. Right? And we could definitely solve it in order V squared E time using Bellman-Ford, right? We just take V steps of Bellman-Ford and deal with a graph on any set of vertices, right? We can do better than this. We can do better than this for graphs that are special in some way, right? We can do V times V plus E, V times linear if our weights are positive and bounded, we can use BFS V times.
Or if our graph doesn't have cycles, we could use DAG relaxation V times. Or if our graph had non-negative edge weights, we could get basically V squared log V plus V times E. Right? And that's actually not bad. In sparse graphs, this is what Bellman-Ford would give us. But if we had Dijkstra's, for example, if we had all positive neg- edge weights or a non-negative, sorry, we could get V squared log V plus V VE time. This is V times Dijkstra. Okay. So, how do these running times compare? This is V times Bellman-Ford. This is V times Dijkstra. In a spot Let's Let's just get a feel for this separation here.
If if we had a sparse graph where V is upper bounded by the number of vertices, this one looks like V squared log V. This one looks like V cubed. And we need to spend at least V squared time. Right? So, actually this is really close to linear in the size of the graph, just off by a log factor, just like sorting would entail. And this one would have a linear factor, right? In the sparse graph, this would be a a linear factor worse than this instead of a logarithmic factor. Again, this linear to log separation. We don't want to have to do this running time if we don't have to. Right? That's the name of the game.
And really all we're going to do in this lecture is try to solve how we can make this running time faster by doing something a little bit more intelligent than running a single source shortest paths algorithm from every vertex. Okay? Uh How are we going to do that? Well, we could Let's see. What are we doing? Right. The idea here is if we had a graph, uh should my graph be directed or undirected? I'm not sure. Let's see if we can make a directed graph. Okay. So, here's a directed graph. Why do I not care about undirected graphs? Can anyone tell me? Yeah, it's because uh I don't care about undirected graphs because if I had an undirected graph, I could detect whether it had negative weight cycles in in constant time.
All right, sorry, in in linear time. I could just check each edge, see if it has negative weight. Because a negative weight edge, undirected edge, is a cycle of negative weight. So, I could just if it has any negative edge weights, I can return in linear time that it does, and I can abort or it has only positive weights and I can still use Dijkstra. So, that's all good. So, we're only concerned about needing to run Bellman-Ford on directed graphs that potentially have negative edge weight. Okay, so here's a graph. Let's see. Is this a graph that I want? Sure. Let's say we've got that direction and this direction.
Okay? Say we have a directed graph like this and let's say this is S. This is our source. Okay? And we have weights being two Sorry, weights being four, one one, two, two two, two. Okay? So, this is an example of a graph we might want to run all-pairs shortest paths on. Maybe we also have negative weights in this graph. Okay? In particular, this has a negative weight cycle. I don't want negative weight cycles, so I'm going to make this zero. Okay? So, this graph doesn't have negative weight cycles. Great. That's true. Great. All right, so here's an example that we might want to compute shortest paths on.
There's no S in all-pairs shortest paths, but I'm going to be talking about a couple shortest paths from S in my next argument. So, I'm just labeling that uh vertex as S. Okay, the claim the the approach we're going to do, we're going to try to take a graph that has negative edge weights directed graph. We don't know if it has negative cycles or not yet. But we want to compute all-pairs shortest paths not in this running time, but in this running time. How could we do that? Well, maybe it's possible that we can change the weight of every edge so that they're all positive, but shortest paths are preserved.
So, basically if a particular path like Okay, the shortest path from S to T here is one, two, three. Right? I could change edge weights uh in this graph. Say for example, if I changed one to zero here that would still make this a shortest path. Right? I haven't done I've reweighted the graph. Shortest paths have to be the same in this graph. But now uh Sorry. Yeah. Uh this is not a shortest path. Okay, I'll make that n minus two. And then these both two and I think and this four. Man, I really should have done my example beforehand. Okay, so this still doesn't have negative weight cycles. It has a negative weight edge.
But this path is longer than this path. So, when this was one this had length of three, which was shorter than this path that is length four. Okay. Cool. So, this is the shortest path from S to T. I could change weights in this graph. For example, changing two to three and one to zero. That changed weights in my graph, but shortest paths remain the same. So, maybe there's a way I could reweight my edges so that shortest paths stay the same. Shortest paths are preserved. Okay? So, I'm going to put this back to where it was. All right. So, idea. Make edge weights non-negative while preserving shortest paths.
Okay? In other words, just reweight the edges here so that shortest paths in G This is G. After we reweight will go to some graph G prime with the same combinatorial structure, just different edge weights. And we want shortest paths we want these weights to all be non-negative and we want shortest paths. If there's a shortest path in G, it continues to be a shortest path in the reweighted graph. That's the goal for today. If we can do that transformation and this is non-negative then we're done. Right? We're done because we can just run Dijkstra V times on that new graph. Get the shortest path distances.
Construct a shortest path tree from those distances and then traverse that tree in the original graph and compute shortest paths along that tree. So, that's that's the claim. Claim. We can compute distances in G So, we're going to restrict G prime to have with non-negative edge weights. It If we have a such a G prime with non-negative edge weights, we can compute distances in G from distances in G prime in V times V plus E. Okay? Which is smaller than our Dijkstra running time. Right? This is our Dijkstra running time. And this is smaller than that. So, that would be fine. Right? What do we do?
We have our new graph G prime. It has all positive edge weights, so we run all-pairs paths in here by just running Dijkstra V times. And then for each vertex S we have some shortest path tree to all the things that's connected to. Right? We can look at that path in G. This is the same combinatorial graph just with different edge weights. We can look at that same tree. I'm not going to be able to draw the exact same tree here. Okay? But what I can do is I can just BFS or DFS along this tree. And every time I have an edge because each one of these is a shortest path in this tree, I can just compute every time I traverse an edge what its shortest path distance is in G in linear time for that vertex, for that particular S.
I do that over all S's. And I get this running time. Okay? So, that's the goal here. All right, so we first wanted to find We were wanting to make edge weights non-negative while preserving shortest paths because if we could do that, we could solve our original all-pairs shortest paths problem. Okay? So, this is the proof sketch. But how can we do this? But how? It doesn't even seem like this could be possible generally. Right? How can I just reweight the edges and maintain that the shortest path trees are the same? That seems like hard to do. And in particular if there are there's a negative weight cycle in this graph, it's impossible to do.
Right? So, claim. Not possible if G contains a negative weight cycle. Okay, the exclamation point is just my comment here. So, if G contains a negative weight cycle, then in particular the shortest path distance or a shortest path in G Right? If this is G. Say we have a a negative weight cycle directed cycle C here. In particular, the shortest path from this vertex on the cycle to this vertex on the cycle, will what is its shortest path? It's infinite. Any shortest path is infinite around this cycle. You just keep going around the cycle over and over and over again because it has negative weight.
Right? Weight of C is less than zero, strictly. Right? That's what a negative weight cycle is. Okay. So, the shortest path A shortest path from S to T has infinite length and in particular is non-simple. However, so so shortest path from shortest path from S to T is non- simple. But, as we proved in the last lecture, shortest paths in a graph with non-negative weights are what? Are simple, right? Cuz there exist shortest path trees. So, that's a contradiction. So, this is not possible. Okay. So, given a graph with negative weights but no negative cycle, it's still not clear how we could find such a reweighting of the graph.
Can we do this? Well, we're going to exploit a little idea here. How can we transform the weights of a path? Well, how What's a a silly idea? I have this silly idea. If I don't want negative edge weights in this graph, uh this is messy in the back. We got edge weights 1 - 2 0 1 4 5 and 1. There's only one negative edge weight here. What if I just added a large number or in particular the the negative of the smallest edge in my graph to every edge in my graph, then I'll have a graph with non-negative weights. Fantastic. Why is that not a good idea? Well, in particular, if I did that to this graph, if I added two to every edge, the weight of this path, which was the shortest path, changed from weight three to weight nine because I added two for every edge.
But, this path, which wasn't a shortest path in the original graph, it had weight four, increased only by two. Now, that is a shortest path or it's a shorter path than this one, so this one can't be a shortest path. Right? So, that transformation sure would make all the edge weights non-negative, but would not preserve shortest paths. Right? In particular, if I added the same edge weight to every edge, I will bias toward taking paths that have fewer edges, not just smaller weight. Okay, so that first idea doesn't work. Right? Idea. Add large number to each edge. This is bad. Uh makes weights non-negative, but does not preserve shortest paths.
So, this is a not uh good idea. Bad idea. Is there any way you can think of to modify the edge weights in a graph in any way that will preserve shortest paths? So, here's a an idea for you. Which is kind of this critical step in Johnson's and a lot of graph transformation algorithms. If I have a vertex, say this middle guy, say V, every path from V goes through an outgoing edge of V. And every path going into V goes through an edge going into V. I haven't said anything I've said very stupid things. But, that observation is critical here. If I add a number or let me see if I got this right in terms of adding and subtracting.
If I add a number to all outgoing edges from a vertex and I subtract that same number from all uh from the weights of all of the incoming edges to that vertex, then every path from V is changed by the same amount because every path from V goes through one of those outgoing edges. And any path going into V has also changed by the same amount. In particular, it's changed by uh a negative whatever we added to the outgoing edges. So, such a transformation adding a number from all the outgoing edges from a vertex and subtracting that same number from all the incoming edges preserves shortest paths.
That's the claim. Idea. This is a better idea. Given vertex V, add I'm going to put this on two lines. Add weight H to all outgoing, yeah. Outgoing edges. And subtract weight to all incoming edges. So, that's the idea. And the claim is this transformation, you know, shortest paths are preserved. Preserved under this transformation. And why is that? It's kind of the exact same argument that I had over there, right? Proof. Consider any path in my graph, right? Either if the path Path could go through V many times or it could go through V not at all. If my path, if I if I have a path in my original graph G, then with with path weight W of pi, right?
This is my path. It goes through uh V some number of times. Okay? So, I'm going to say this is going from S to T. If it crosses V if it never crosses V, if it never it touches V, the the vertex that I transformed, then I argue that the path weight is the same, right? Because I didn't do anything to edges that are in this path. Alternatively, this thing goes through V sometimes. If it goes through V in the middle, how is the weight of my path changed? Well, it hasn't, right? Because I added a number to all outgoing edges, so there's an outgoing edge here with weight I've changed by weight H. And there's an incoming edge here that I've changed by weight negative H, so these cancel out and you you got zero.
Right? So, passing through a vertex doesn't change the weight of my path. The only way I could change the weight of my path is if V is the start vertex or the end vertex. Right? So, it's possible that S is my vertex or T is my vertex. Well, for any vertex for any path leaving V, I will have increased the weight of that edge that that path by H, right? Because I added a weight H to all outgoing edges. So, again, while the path weight has changed, since all of the paths leaving V have changed by the same amount, a shortest path will still be a shortest path. And same goes for T. If T, the end vertex, is V, I'll have subtracted H from all of my incoming edges, which means that any path ending at T, any directed path ending at T, also changes by the same value, and so shortest paths will must be preserved.
So, shortest paths preserved. So, that's pretty cool transformation. I can assign for any vertex such a transformation, which affects all of the edges surrounding it, right? By by this H additive factor. Either added or subtracted. So, maybe And I can do this independently for every vertex, right? If shortest paths were preserved by me doing this to one vertex, then if I do it to another vertex, then shortest paths are still preserved. And let's let's prove that real quick. Okay? What I'm going to do is I'm I'm going to want to do this to give me flexibility for changing all the edge weights in my graph to have this property.
I'm going to set or define a potential function H that maps vertices to, you know, integers. So, this is the potential H of V. Okay? And then we're going to make a graph G prime based on above transformation for each vertex in V. Okay? So, I'm going to set a number a an H for each vertex. These are independent now. And I'm going to add that potential to all outgoing edges, and I'm going to subtract that potential from all incoming edges. This transformation's going to preserve shortest paths. Let's let's actually be a little bit more rigorous that that's the case when we do this multiple times.
Okay? So, claim shortest paths are still preserved. All right. Well, that's again not so difficult to see. Let's con- consider a path from S to T. Passes through a bunch of vertices. I'm going to label these as V0 to VK so that I can kind of number them. All right. This is V1 here. This is a directed path. Okay? V1 2 3 4 5 all the way up to K. Okay? There are K edges in this graph. Right? I claim to you that any path from V0 to VK, any shortest path from V0 to VK, remains a shortest path after I re- reweight everything in this way. Okay. So, let's say this is path pi, and so it has weight W pi, which is really just the sum of all of the edge weights from VI - 1 to VI for I equals 1 to K.
Right? This is poor notation. This is the weight of the edge from VI - 1 to I. Right? And we've got our indexes from 1. That's the first edge to K, which is the last edge. Right? So, that's the weight of my path. The weight of my transformed path, I'm going to do it down here. It's a little iffy. The weight of my transformed path, I'm going to say is the weight in this new re- re- weighted graph G prime. Okay? This weight of that same path, right? It's the same path. It's just going to be the sum of all of the reweighted edges. So, I equals 1 to K. Of my original weight of my edge, so from 0 I - 1 to V I.
But what did I do? This edge is outgoing from VI - 1. So, it's outgoing, so I add that weight that that potential, sorry. But that edge is also incoming into VI, right? So, when I reweighted the thing, I got a subtraction of H V I. Okay? Now, what happens here in the sum? This term, if I just took the sum over this term, that's exactly my original pathway. Right? So, that's good. But you'll notice that this sum has K terms, and this sum has the subtraction of K other terms, but most of these terms are equal. Right? Along the path, all the incoming and outgoing edges cancel out. Right? So, we're left with only adding the potential at the starting vertex and subtracting the potential at the last final vertex, right?
So, we've got add H V0 minus H V K. And why is that good? Well, that's good because every path from V0 to VK starts at V0 and ends at VK. That's just that's how it is. That's how we've defined paths going from V0 to VK. But every such path, we transform the weight of that path by adding a con- by adding a constant associated with the start and adding this value associated with the end. And so, every path going from V0 to VK changes by the same amount. Right? And so, if this path P uh pi was shortest, it's still shortest in the reweighted graph because I've just changed all paths between those two vertices by the same amount.
It's This is kind of like a telescoping argument here uh in in that kind of proof. Right. So, we have uh the weight changes, right? It could change, but it changes all paths between these two vertices by the same amount, which means that shortest paths are still shortest. Awesome. Okay. So, the name of the game here is now we have this really flexible tool. Right? We have this tool where we can add or subtract weight from various edges, but we have to do so in a kind of localized constrained way, right? We have to do the same thing around each vertex. But it seems like a powerful transformation technique that maybe we can get this this thing that we want, which is a G prime, a reweighting of the graph where all the edge weights are positive or non-negative.
So, does there exist an H such that the weights are all positive? What does that mean? W prime UV, right? The weight in my new graph, in G prime, I want these modified weights, right? This modified weight of my graph, I want each of these to be non-negative. So, does there exist such a thing? Huh. Well, if I rearrange this equation a little bit, this side, I get something that looks like this. h of v needs to be less than or equal to h of u plus uh the weight of some edge from u to v. Huh. What does that look like? That looks like almost exactly the definition of the triangle inequality. Right?
Shortest path from some vertex here and it's shortest path distance from the same vertex here, this is just a statement of the triangle inequality. Right? So, if we can set these h's to be the shortest path distance from some vertex and those shortest path distances are finite and non not minus infinity, then this thing will hold by triangle inequality and in particular, if we were to reweight the edges based on those values of h, then we get new edge weights that are non-negative. Awesome. Okay. But, there might not be any vertex from which we can access which is which we can reach all vertices in the graph, right?
In particular, my graph might not even be connected. Right? If I want this property, I need all of these I don't gain any information if these things are infinite. Right? I It's exhaustively true. Infinity is I I don't even know how to compare it infinity and infinity plus a constant. I I I don't know, right? So, I need all of these things to be finite. So, how can I make those things finite? So, here's the next idea. Add new vertex s with zero weight edge to every vertex v in v. Right? We take our original graph. We add a new super node or auxiliary vertex s with a zero weight edge to every vertex in my graph, right?
What does that look like? This is like there's my original graph. And now I have this vertex s, but it has directed edges into all of the vertices with zero weight. That's our picture and this new thing right? I'm going to call maybe my s graph now. All right? And the claim is well, now if I run some shortest path algorithm, single source shortest path algorithm this time, from s to compute the shortest path distance to all of the vertices, the shortest path distance to each of the vertices can't be positive, right? Because there's a zero weight edge, so a minimum weight path is going to be no bigger than zero.
If it's finite, then there's a finite length shortest path. If it's minus infinity, then there's a negative weight cycle in my graph and I can stop. Right? Okay. So, there are either two situations. If delta s v equals minus infinity, so I guess this is run single source shortest paths from s. And really, because this graph could contain negative edge weights and could contain negative cycles, we can't really do better than running Bellman-Ford here, right? From s to compute these paths. If there exists in this new graph, this gs, if there exists a vertex that has negative infinite weight in the reweighted graph, sorry.
Uh uh in the original graph g, g hasn't been reweighted yet. If there's a negative weight distance from s, then it uh then there was a negative weight cycle in the original graph. Why is that? Well, if this was set to minus infinity, then there is some negative weight cycle in the graph, right? The worry is that that negative weight cycle was added to my graph by adding this vertex s. But, what do I know about vertex s? It has no incoming edges, right? So, no negative weight cycle could go through s. Right? So, any negative weight cycle was in the original graph and so I can abort. Abort. Yay.
Otherwise, what do I do? Well, I know these shortest path distances here would satisfy the triangle inequality. Right? So, if I reweight uh with h of v equal to delta s of v, right? If we set our potentials in our reweighted graph to be the shortest path distance from our super node s, it it satisfies the triangle inequality, right? And because there's no negative cycles, all of these values are finite and then this reweighting will lead to a graph with strictly or not strictly uh strictly no negative weights or uh non-negative weights. Okay, great. So, that's basically it. That's the idea behind Johnson's algorithm.
It's really a reduction problem, a reduction algorithm. We're reducing from solving kind of signed all pairs shortest paths, graphs where their weights could be positive or negative, and we're reducing to creating a graph that has the same shortest paths properties, but only has non-negative edge weights. So, we're reducing from a signed context to a non-negative weight context, right? So, Johnson's algorithm, what are the steps? Construct g s from g. Right? Just as up here, right? I make a new vertex s. I put a zero weight directed edge from s to every vertex. Okay, so that's the first step. Second step, compute d s v for all v in v.
i.e. or e.g. I guess really it should be i.e. because I don't really have another option here, but by Bellman- Ford. This is just a single run of Bellman-Ford here. Compute. And then there are two possibilities. If there exists a delta s v that's minus infinity, then abort. Else, make a re- reweight the graph according to this reweighting scheme, right? By reweighting each edge in my original graph to have weight our new weight, which is our old weight plus our transformation. Now, our transformation is now going to set HV to this delta SV, right? So, I'm going to add delta SU and subtract delta SV.
That's our re-weighting scheme. I'm just identifying HV with this shortest path distance here. Okay? And I after I re-weighted that, I can just solve all pairs shortest paths on G prime with Dijkstra. And then compute G shortest path distances from G prime shortest path distances. Right? Compute these distances from the other using this algorithm up here. Can compute distances in G from distances in G prime in linear time. Or, sorry, V times linear time. Linear time for each S, for each vertex in my graph. Okay. So, that's the algorithm. It's basically correctness is trivial, right? We already proved the whole part of this lecture, the interesting part of this lecture, was proving that if we had a transformation based on a potential function that changed outgoing edges in a symmetrically opposite way as incoming edges, then that preserves shortest paths.
And then realizing that the triangle inequality enforces this condition that edge weights will be positive or non-negative under this re-weighting, so we find shortest path distances from some other arbitrary vertex and set our potential functions to be those shortest path distance weights. We do the re-weighting because that re-weighting preserves shortest paths, which we already argued. Right? Then we can do then then this has positive edge weights, so Dijkstra applies. And then computing this takes a small amount of time. Okay, what is the running time of this algorithm? So, this part, reconstructing this thing, this takes linear time, right?
I'm just adding I'm just making a new graph of the same size except I added V edges and one vertex. Okay? Computing Bellman doing Bellman-Ford on this new modified graph, that's just I'm doing that once. That takes V times E time. Doing this check, that that just take I'm looping over my vertices, that just takes V time. Otherwise, doing this re-weighting, I change the weight of every edge, that takes order E time. And then solving G prime uh solving all pairs shortest paths on the modified edge weight graph with Dijkstra takes V times Dijkstra. Right? That's uh Use a little bit more board space here.
That's V times V uh log V plus E time, right? Which is actually the running time that we're looking for. Right? I wanted to reduce to not using more than this time. We used this amount of time. Let's make sure we still didn't use even more. After that, we compute these paths as proved before in V times V plus E, which is smaller than that, right? And so summing up all of these running times, this one dominates, and so Johnson's can solve signed weighted all pairs shortest paths. Signed all pairs shortest paths not in V times Bellman-Ford like we had before up here, but faster in nearly linear for sparse graphs just without this log factor.
So, we got a a quite a big improvement. Right? So, that's the nice thing about all pairs shortest paths is that really we don't have to incur this this big cost uh in the context of negative weights. Essentially, we just run Bellman-Ford once to see if there is a negative weight cycle in my graph. If it is, I save a lot of work by stopping early. Okay? So, that's Johnson's. That's the end of our graphs lectures. Uh we'll be having a review and problem session uh about how to solve problems, graph problems, using this material. But we've we've talked about a lot of different things. So far, we've talked about graph reachability, connected components, detecting cycles, detecting topological sort orders of a DAG.
We've talked about finding negative weight cycles, single source shortest path algorithms. And now, finally, today, all pairs shortest path algorithms with a new algorithm that's really not a an entirely new algorithm, right? We didn't have to do any proof by induction here. Really, the heavy work that's happening is we're reducing to using either Dijkstra or Bellman-Ford to do the heavy lifting of finding single source shortest paths efficiently, right? So, Johnson's is really just glue to uh transform a graph in a clever way and then reducing to using some of these shortest paths algorithms faster.
Okay? So, that's our unit on graphs. Uh our next lecture will start talking about a general form of not presenting you with an algorithm, but how to design your own algorithm in the context of dynamic programming. Okay? So, see you next lecture.