Transcript

Hi everyone. Welcome to the uh 11th lecture of 6.006. Uh our first lecture on weighted shortest paths. Uh until uh now, we've only been talking about graphs that uh where we measure distance in terms of the number of edges in a path, right? Today, we're going to generalize that notion, but I just want to go over what we've talked about in the last two lectures. Uh in the last two lectures, we've talked about two algorithms, breadth-first search and depth-first search, to solve a range of problems. Here's some of the problems that we've uh been solving, single-source shortest paths, uh where distances are measured in number of edges in a path, uh and we use a BFS to solve this problem, starting from a single source, usually a vertex S that we we call.

Uh and and we solved that in linear time, right? And we solved that in order V plus E. That's what you we called linear time for a graph. For the special case of single-source reachability, here we had to return a shortest path distance for every vertex, and there was at most E things reachable from a vertex. So, this is uh the bound we got, but in the special case for single-source reachability, when our output only has to list the vertices that are reachable from me, the the number of things reachable in a uh uh basically a spanning tree of the connected component of my source can at almost be of order E.

And so, for all the little singleton vertices in my graph, I don't really care. Right? So, I can get this in order E, but that's kind of a a little optimization. Uh the next thing we did was we talked about connected components, and we didn't just reduce to using a search algorithm like a single source reachability algorithm like BFS or DFS, we put a for loop around that to explore the entire graph by basically saying if I've explored one connected component, then uh I can look at any other vertex I haven't seen and explore the next one, right? And so, that actually with some a little analysis, also got linear time because I'm at most traversing any component of my graph once.

That's kind of the the idea. And then uh and we can use that using BFS or DFS, really, because we're just trying to get a thing that searches an entire connected component. Uh and then this topological sort we did at the end of the last lecture, we used full DFS to give an ordering of the vertices in a DAG. I maybe I'll specify clearly that this is only for a DAG, right? Where we uh have an ordering of the vertices, so all the edges go forward in that order, for example. Okay? And that we also did IN LINEAR TIME. ALL RIGHT. IN THIS LECTURE, and in the actually the next four lectures, what we're going to do is instead of measuring distance in terms of the number of edges in a path, so previously distance equal number of edges, we're going to generalize that notion, so instead of counting an edge, we're going to count an integer associated with that edge.

It's going to be called a weight, all right? So, here's an example of a weighted graph G, and I've labeled in red weights for each of these edges. This is a directed graph on eight vertices, and I've got a integer associated with each edge. You'll notice some of them are positive, some of them are negative. It's okay to be zero as well. It's just any integer edge weight here. So, generally, we're going to be Along with our graph G, we're going to be given a weight function that maps uh the edges of G to we're going to say integers. Okay? In this class, anyway. Uh in other contexts in mathematics, you might have this be real numbers, but in this class, we're going to deal with integers.

So, each edge, if you have an edge, we're going to say this is the edge weight the weight of this edge E from E. We We might sometimes if if this edge E is UV, right? We might sometimes say the weight from U to V, since we have a simple graph, that's unambiguous, right? All right. So, but this is just talking about our notation. So, in general, for example, the weight from vertex B to F in this graph is what? Can someone tell me? Minus four, right? It's right here, and I'll be consistent with my coloring, cuz I've got colored chalk today. Minus four. Happiness. All right. So, why do we care about adding weights to our graph?

Well, this comes up a lot in many applications. For example, you know, distances in a road network, right? If I have a road from here, uh so so from Mass Ave, uh front of MIT to Central Square, we might think of that as one road. Maybe maybe you've got uh oh each road is a connection between two intersections in my road network. But an edge, it takes longer to go from, say, Vassar Street to Amherst. That that takes a shorter amount of time than it does to go from Memorial Drive across the river to Beacon Street, right? So, we might want to associate a larger distance or a weight associated with that edge, right?

Uh latency in a in a in a network, for example. Maybe strength of relationships in a social network. And you could imagine that it's possible maybe you're frenemies with someone, right? Like you you don't like them. And so maybe you have a negative weight associated with uh an edge in a social network. I'm not sure. May maybe not. But there are lots of applications where you might want weights on your edges. So, that that comes to the next question of how do I represent How do I give the user, or the algorithm, these weights in my graph, right? We had a representation rep- representation for a graph, right?

Our common way to represent a graph was store a set data structure on the vertices mapping to the adjacencies of each vertex, which we stored in what we called an adjacency list, which really could be any data structure, right? Uh commonly it's just a a an array uh of the adjacencies, but you could also have that be a uh uh set data structure where you can query in constant time uh what if a particular adjacency exists in that graph. So, a common way There are two kind of common ways to store these weights. One is just with every adjacency, I'm going to store its weight. Maybe just in a tuple, something uh you know, with each adjacency also store weight of the edge that it corresponds to, right?

Just in any way, right? Uh a second way instead of trying to modify our graph structure that we gave you before, let's just have a dictionary of all the edges mapping to their weights, right? And we already know how to do that. Just any set data structure, any separate set data structure mapping edges to their I guess weights. Bad notation, but you get the idea. Okay? Uh and it doesn't really matter how we're doing this. The The assumption that we're going to rely on here is that we given an edge right? Given this vertex pair, I can query what the weight of that edge is in constant time, right?

And so, if I'm going to do that, I can either store it with a maybe a hash table of hash tables, right? A hash table uh mapping uh the set of vertices to their adjacencies, and then each adjacency list stores its adjacencies in a hash table, and that way in constant time I can check what the weight is there. Or here, I'm just I could even have just a single hash table mapping the pair, the the edge, the tuple, constant size, uh to its weight, right? So, either way is fine. Uh we're just going to assume that we can query an edge in constant time. The weight of an edge in constant time. Okay, so this is a that graph uh example.

Uh it's a little busy here. I'm probably going to erase that in just a second. Uh but we're going to move on to what giving these edges weights implies for uh kind of these problems that we've defined in terms of unweighted graphs, right? In particular, we're going to be concentrating on single source shortest paths again. At least for the next three lectures, we'll generalize that even still uh in the uh in the next lecture. I mean, in the fourth uh in three lectures from now. But what we had here was that the distance before, in an unweighted graph, was the number of edges in the path. Here, we're going to generalize that notion, kind of obviously, to weighted paths, right?

And the weight of a path, I'm going to call it pi, so some uh uh weight of path pi, right? It's just going to be the sum of the weights in the edges in the path, right? So, edge in the path, I'm going to sum their weights, right? So, that's all this the weight of a path means it's just I'm going to sum all the weights in a path. So, if I took a look at the maybe there's a particular path here, the path from A to B to F to G, right? Is going to be -5 -4 2 that's going to be -9 + 2 is -7, right? Okay? So, just as an example. So, uh then then uh what is the shortest path then? Well, kind of obviously among all paths between two vertices, it's going to be one with the minimum weight, right?

Yeah, question. Can I use the same edge more than once? Can I use the same edge more than once? Uh right now uh you're asking about the distinction uh in in our class, which we have between paths and simple paths, right? So, here a weighted path doesn't really care if we visit an edge more than once, right? So, if an edge appears more than once in pi, we have to count that more than once in the edge weight in the weight of the path. Okay, great question. Um uh but what we're going to see later on is shortest paths cannot repeat an edge more than once. Uh in in certain contexts, right? So, so we're going to get to the the problem there a little later in this lecture and we're going to solve that in tomorrow's lecture, but if you have uh we're getting a little ahead of ourselves, but uh when we have negative weights in a graph, it's possible that things go wrong.

We're going to get there in about five lines. Okay, great. So, uh the the sh- a shortest path and in this case, I'm going to clarify that this is the weighted shortest path, right? Uh is a minimum mini mum. Sure. Uh is a minimum weight path you know, from S to T. Right? Nothing too interesting here, but there's actually some subtleties we have to deal with here. Right? Uh we're going to call just like we did with uh uh breadth-first search when we talked about shortest paths, we're going to define the uh uh uh uh uh an expression for what the distance or the shortest uh path weight is between two vertices.

And that's going to I'm going to represent that by a delta, right? A delta from a vertex S to T is going to be Let's I'm going to do the wrong thing first. The minimum over the weight of all paths for all paths pi from S to T. Okay. So, there's a couple things that go wrong here. First thing that goes wrong is the same thing that went wrong with breadth-first search, right? Anyone remember what could go wrong with breadth-first search for this delta definition? There is no path. Maybe there's no path, right? Right? So, if the in the except if no path just by convention, we're setting uh delta ST to equal infinity.

But, there's one additional problem with weighted shortest paths. and it's a little subtle, it's possible that a finite shortest finite length shortest path doesn't exist. And what do I mean by that? It means uh I could keep going through edges in my graph and continually getting a shorter path, right? So, if I can if the shortest the minimum weight of a path from S to T actually goes through an infinite number of edges, then this isn't really well-defined, right? So, I'm going to change this minimum here to uh in in mathematics we would just to be specific, we call it an infimum, right? So, if in the case where there where the uh the weight of a shortest path can approach arbitrarily small, right?

Then we'll call this thing minus infinity, okay? So, when does that occur? When does that occur? When could we have our shortest path go through lots and lots of vertices? Well, let's actually take a look at this example here. Can someone tell me what the shortest path is from A to actually any vertex in this graph? E F G C Ah, okay. So, well, we could look at this this path I have to B. Let's just take a look at B, right? I have a path going from A to B that is minus five. Okay, that's pretty good. That's pretty small, right? And it seems that if I go around this graph through another way, it might be bigger, right?

So, I go at 7 + 3 + 8. That's 15 - 1. That's 14. That's That's much bigger than my -5. So, it seems like -5 should be good, right? Anyone have a problem with this path or problem with this being the shortest path? And what your colleague just informed me was that there is something interesting happening here in this graph in particular. We have a cycle from B to F to G to C that has negative total weight, right? Back back to B, right? This has -4 + 2 + 1 -1, right? So, that total cycle has a cycle weight of -2, right? This is negative weight cycle. So, uh if I want to get to B, I could go there via this -5 weight edge.

But every time I circled around this cycle, I incur -2 to my path weight, right? So, I just keep going around this cycle over and over and over and over and over and over again, and I don't have any finite length minimum weight path, right? And in such cases, we just say that delta is minus infinity, right? So, uh the the problem here is that uh we could have negative weight cycles. deserves a capital letter. Negative weight cycles. It's a problem. Okay? Uh in particular, uh, if there exists a path from S to some vertex V that goes through a vertex on a negative weight cycle then I can take that path to that vertex, circle around the negative weight cycle, and then proceed to V, and I can take that cycle as many times as I want.

Then, this delta SV we're going to set to minus infinity. Okay? And in such cases, in our shortest paths algorithm, we don't really care about what the shortest path is, right? We're not even going to deal with parent pointers here, right? Cuz there is no finite length shortest path. So, I'm going to just going to kind of throw up my hands in the air and say, "You know what? I can't return you a shortest path, but I might want to return to you a negative weight cycle, right? If you told me that this thing has bad weight, right? Maybe I want you to tell me what a path is that goes through a negative weight cycle to get back to S." Right?

So, that's what we're going to talk about next lecture. This lecture, we are not going to talk about that. We are going to talk about weighted shortest paths, though. That's what, uh, the remainder of this, uh, this unit on graphs is really about is weighted shortest paths. Okay. So, in weighted shortest paths, we actually know an algorithm already to solve a subset of weighted shortest paths, namely BFS, right? Now, you're like, "Wait, Jason. BFS doesn't solve weighted shortest paths. We didn't even know about weighted graphs then, right? How does that solve weighted shortest paths?" Well, there's a couple cases where we might be able to reduce to solving shortest paths using BFS.

Can anyone think of such a scenario? Uh so, let's say, I mean, kind of what we did before was we counted the number of edges, right? So, if we gave a weight of one to every edge in my graph, then just that graph, that weighted graph, corresponds to an unweighted graph using the other distance metric, right? So, in that case, BFS just solves our problem. And in In fact, we can generalize further. What if all of our weights were positive but the same value, right? If it was all positive in the same value, then we could just to, you know, divide by that value. Right? Now, we have a weighted an unweighted uh graph, which we can run BFS and then multiply shortest path distances by that value later on.

And in fact, there's one further generalization we could make, which is a little bit of a tricky graph transformation problem, but we can also get this linear-time algorithm for weighted single-source shortest paths in contexts where the weights aren't that large. Okay? So, if I have positive edge weights, right? If I have a positive edge weight that's say using using my weight color here, that's like weight of four, right? That's that's kind of problematic because I don't know how to simulate that using an unweighted graph. Or do I? Anyone have an idea of how I could simulate uh an edge of weight four with an unweighted graph?

Yeah. Have four edges of weight one. Yeah, I can just put four edges of weight one in parallel here. Like sorry, in series, the opposite of parallel. Okay? I can just convert this here into 1 2 3 four edges. And if I do that for every edge in my graph and we have positive edge weights, then that that transformation can hold. Now, that's not necessarily a good transformation to make. Why? Wait, the weight might be very big. Yeah, the weights might be very big compared to the number of vertices and edges in my graph. However, if the sum of all weights in my graph is asymptotically less than V plus E, right?

We can get a linear time algorithm again by reducing to BFS. Okay, so that's great. Today, uh but but in general, that that gives us a linear time algorithm in these in these very special cases. Uh and in general, it's an open problem. We don't know uh whether we can solve the single source single source shortest paths uh problem in the weighted context for general graphs. problem in for general graphs in linear time. We don't know how to do it. Right? But, uh, what we do know are some algorithms that do pretty well and that's what we use all the time. Uh, but in the one more special case we're going to go over today is when we have this really nice structure where we have a DAG, a directed acyclic graph like we were talking about in the last lecture.

We can actually for any set of edge weights, right? Remember with BFS we kind of we needed to restrict our edge weights to be positive and maybe bounded to get this good running time. Uh, for any set of edge weights, if our our graph structure is a DAG, really has nothing to do with the weights. If the graph structure is a DAG, then we can actually solve this single source shortest path problem in linear time. Which is pretty awesome. Right? Now, for general graphs, we're going to show you in the next lecture how to for any graph, even with cycles, even with negative weight cycles, we're going to show you how to solve this single source shortest path problem in something like a quadratic running time bound.

Now, this isn't the best known, but it's a really practical algorithm and people use it all the time. Okay? And and it we are going to show Bellman-Ford in the context of the DAG algorithm we're going to uh, solve today. Okay? So, that's the very general case in terms of restrictions on our graph. But, in reality, most problems that that come up in applications occur with graphs that have positive edge weights. Okay? You can think of a road network. You've got or non-negative ones not ever useful to kind of go back to where you came from because you want to make progress to where you're going.

Okay? So, in the context where you don't have negative weights, you don't have this problem where you have negative weight cycles, we can actually do a lot better by exploiting that property. Uh and we get a bound that's a little bit that looks a little bit more like n log n, right? Like it's it's pretty close to linear. You're losing a log factor on the number of vertices. Okay? But, it's pretty good. This is called Dijkstra and we'll get to that in two lectures. Okay. So, that's kind of the road map of what we're going to do for the at least the next three lectures. Uh but before we go on to showing you how to solve single source shortest paths in a DAG using this algorithm called that I'm calling DAG relaxation here, uh I'm going to go back to a a thing that we talked about in breadth-first search, where in breadth-first search when we solve single source shortest paths, we output two things, right?

We output single single source shortest paths, these deltas, right? For the other definition of distance, you know, the weights. I mean, not the weights, the the distances, the shortest distances. Uh but, we also return parent pointers, right? We return parent pointers back along paths to the source, along shortest paths, right? We call this the shortest paths tree. So, I'm going to revisit this topic of shortest paths tree, shortest path trees. Shortest path trees. Okay? And in particular, it's kind of going to be annoying to talk about both of these quantities, right, distances and parent pointers, as we go through all three of these algorithms.

Right, it's basically going to be bookkeeping to Distances are actually sufficient for us to reconstruct parent pointers if we need them later. Okay? So, what I'm going to show for you prove to you now is that if I give you the shortest path distances for the subset of the the graph reachable from S that doesn't go through negative weight cycles, right? If I'm giving you those distances, I can reconstruct parent pointers along shortest paths in linear time for any graph I might give you if I give you those shortest path distances. Okay. So, that's what I'm going to try to show to you now. Uh So, here's the uh uh algorithm uh for weighted uh There's the caveat here I'm going to write down for weighted shortest paths only need parent pointers for V with uh finite shortest path distance.

Okay? Only finite shortest path distance, right? We don't care about the infinite ones or the minus infinite ones, just the finite ones. Okay. So, here's the algorithm. I'M GOING TO INITIALIZE ALL PV to equal uh sorry. Oh. Getting ahead of myself. I'm down deck. All right. Uh Uh in it all in it my parent pointer data structure, right? To be empty. Okay? Right? I First I'm not going to store any parent pointers, but at the beginning I'm going to set the parent pointer of the source to be none. Right? So, that's what we kind of did in breadth-first as well, right? Now, what I've given you is I'm I'm trying to show that given all the shortest path distances, I can construct these parent pointers correctly.

So, what I'm going to do is for each vertex U in my graph where my delta S of U is finite. What am I going to do? I'm going to say, "Well, let's take a look at all my outgoing neighbors." Okay? This is kind of what we do in every graph algorithm. For each V in the adjacency the outgoing adjacencies of U if there's no parent pointer assigned to this V right? There's the potential that I you I I you this you this vertex you is the parent of V. It's possible, right? It's an It's some incoming edge to V. Okay? When would it be an incoming edge to V? If I haven't said if uh V not in P, right? I haven't assigned it a parent pointer.

And so, this means it could be my parent. When is it my parent? Along a shortest path. Sure. Sum of the distance along the edge to the distance to the other. Yeah, so we have some edge from U to V. It has some weight, right? If I know already know the shortest path distance to U, and I know the shortest path distance to V right? If the shortest path distance from S to U, let's let's draw a picture here. We've got S, we got some path here to U, and we know we've got an edge from U to V. Okay? If this shortest path distance plus this edge weight is equal to the shortest path distance from S to V then it better be I mean, there may be more than one shortest path, but this is certainly a shortest path.

So, we can assign a parent pointer back to U. Okay? Right, so let's write that condition down. If the shortest path distance from S to V equals the shortest path distance from S to U and then traversing the edge from U to V then then exists shortest path that uses edge UV right? In particularly in particular this one right? So, set the parent of you of V to you. Okay. So, this is the algorithm. I'm not going to prove to you that this is correct, but it kind of intuitively makes sense, right? If I have these shortest path distances, right? You can prove by induction that not only does this parent pointer point to the right place along some shortest path here, right?

But, it also does so in linear time because I'm looping over all the the vertices and looping over its outgoing adjacencies once. Same analysis as we had for both BFS and DFS, essentially. Right? And then, since we can do this, since we can compute parent pointers from these distances, we're going to kind of ignore computing these parent pointers from now on, right? We're just going to concentrate on computing the distances because, you know, we're going to have to take linear time anyway, right? At least. And all these other things take more time, so we can compute the distances in more time and then compute the parents after.

Okay. So, that's what we're going to do. Okay. So, now, with all that build-up, let's show an algorithm, right? How do we compute shortest single source shortest paths in a DAG in linear time? Okay. Well, a DAG I mean, this is actually a super useful convenient thing in algorithms in general. DAGs are just nice things, right? They're kind of ordered in a way, right? There's this topological sort order that we were talking about before. This is going to play a key role, right? There's a really nice structure to DAGs, not having cycles, not having to deal with this negative weight cycle problem, right?

You can only kind of go in one direction along this graph. Right? It's very nice structure to exploit. And so, we're going to exploit it. And here's the idea. DAG relaxation. What it's going to do is it's going to start out with some estimates of what these distances should be. Right? Okay, so maintain maintain distance estimates. And now I'm going to try to be careful here about how I draw my D's. Okay? This is a D. This is a delta. Okay? This is shortest paths. This is a distance estimate. Okay? So, that's what I'm going to be using for the the rest of this time. So, we're going to initialize maintain these uh estimates of distance D, which are going to start at uh initially infinite.

Right? Okay, I don't know what they are. Right? I don't know what the shortest paths are, but they better be less than infinite. Or else I don't care. Right? So, I'm going to That's the kind of worst case scenario. Right? It can't be worse than this. For every vertex and we're going to maintain the property that uh estimates upper bound That should probably be two words. Upper bound uh delta SV uh we're going to maintain that the upper bound is thing and gradually lower until they're equal. Okay? So, this is the idea. We start from an overestimate, an upper bound on the distance estimate. And then we're repeatedly going to lower that value as we gain more information about the graph.

Maintaining that we're always upper bounding the distance. And we're going to keep doing it, keep doing it, keep doing it until, as we we will try to prove to you, these estimates reach actually reach down all the way to our shortest path distances. Okay? So, when do we lower these things? When do we lower these things? We're going to lower these distance estimates whenever the distance at estimates violate what we're going to call the triangle inequality. Okay, what is the triangle inequality? Triangle inequality is actually a pretty intuitive notion. Okay? It's basically saying if I have three points, that's that's triangle.

Right? Uh maybe bigger so I can write a letter in them. Okay, it's basically saying that if I have a vertex U, a vertex V, vertex X, for example, right? The shortest path distance Right? The shortest path distance delta of UV, that's the shortest path distance from U to V. It can't be bigger than a shortest path from U to V that also goes through X. Right? Right? I'm I'm Of Of my paths, I'm now restricting the paths that I have to the ones that go through X. Right? The shortest path distance from U to V can't be bigger than restricting paths that go through X and taking that shortest distance, right?

Getting the shortest path distance from here and adding it to the shortest path distance here, right? Delta UX delta XV, right? I mean, that That's just a statement of I I'm I'm restricting to a subset of the paths, I can't increase my I I can't decrease my minimum distance, right? So, this is the statement of the triangle inequality, right? That the shortest path distance from U to V is can't be uh bigger than the shortest path distance from U to X plus the shortest path distance from X to V for any X in my graph that's not U and V, okay? So, that's the triangle inequality. Pretty intuitive notion, right?

Okay, why is this useful? Okay, well, if I find if I find an edge in my graph if there's an edge UV in my graph such that this condition is violated for the estimates that I have, right? It obviously can't be violated on my shortest path distances, but if it it violates it on the estimates UV is bigger than UX. Uh sorry, U How am I going to do this? I want this to be S. I'm calculating shortest path distances from S. And shortest path distances from S to some incoming vertex U plus the edge weight from U to V. Okay? All right. So, what is this doing? I have some edge UV in my graph. Okay? Basically, what I've said is that I have some distance estimate to U but going through making a path to V by going through U and then the edge from U to V is better than my current estimate.

My shortest path estimate to V. That's bad, right? That's violating the triangle inequality. These cannot be the right weights, right? These cannot be the right distances. So, how we're going to do that is lower This is what we said repeatedly lower these distance estimates. I'm going to lower this guy down to equal this thing. In a sense, this constraint was violated but now we're relaxing that constraint so that this is no longer violated, right? So, that's a I'm I'm Relax is a little weird word here. We're using it for historical reasons, but that's what we mean by when we say relax. This thing is a violated constraint.

It's got some pressure to be resolved, right? And so, what we're doing is to resolve it, we're just setting this guy equal to this so it at least resolves locally that constraint. Now, it may violate the triangle inequality other way else other places now that we've done this change, but at least this constraint is now relaxed and satisfied. Okay, so uh relax edge by lowering D of SV to this thing. Okay? That's what we're going to mean by relaxing an edge. Okay? And relaxing an edge is what I'll call safe. It's safe to do. Okay? What do I mean by relax relaxation is safe? It means that as I am computing these shortest path distances, right?

I'm going to maintain this property that each one of these estimates, sorry. These estimates here has the property that it's either infinite or it is the weight of some path to V. Okay? So, that's that's the thing that RELAXATION IS SAFE. OKAY. SO, EACH uh distance estimate SV is weight of some path from S to V or infinite. Okay? And this is a pretty easy thing to prove, right? If I had the invariant that these were all weights of shortest paths, let's try to relax an edge. Right? And we need to show that this property is maintained. Relax edge UV. Okay? Now, if I relax edge UV, what do I do? I set this thing or sorry, I set this thing, my shortest path distance to V to be this thing plus this thing, right?

This is an a weight of an edge from U to V. Now, by my assumption that we're maintaining that this is a the weight of some path in my graph, right? If this thing is bigger, I'm setting it to the weight of some path in my graph to U plus an edge from U to V, and so this checks out. So, uh uh assign D of S to V to weight of some path. Okay? I I'm not going to write down all the argument that I just said here, but basically since this distance estimate was by supposition before the weight of some path to V to you to to you, right? Then this is again the weight of some path to V. Okay, great. So, now we're ready to actually go through this algorithm.

So, DAG relaxation from over there initializes all of our distance estimates to equal infinity just like we did in BFS. Then set my distance estimate to myself to be zero, right? Now, it's possible that this might be minus infinity or negative at some point. But right now, I'm just setting it to zero. Okay? And either way, zero is going to upper bound the distance to S. Right? So, uh in particular, at initialization, anything not reachable from S is set correctly. And S itself is set as an upper bound to a shortest path distance. Okay? Now, we're going to process each vertex U in a topological sort order.

So, remember, our input to DAG relaxation is a DAG. So, this thing has a topological sort order. We're going to process these vertices in that order. Okay? You can imagine we're starting at the top and all my vertices are all my edges are pointed away from me, and I'm just processing each vertex down this topological sort line. Okay? And then for each of these vertices, what am I going to do? I'm going to look at all the outgoing neighbors, and if the triangle inequality is violated, I'm going to relax that edge. It's the the algorithm is as simple as that. For each outgoing neighbor of V, sorry, of U, I always get U and V mixed up here.

Okay? If my shortest path estimate to V violates the triangle inequality for an edge for an incoming edge, then I'm going to set relax UV I set D S V equal to D S U plus W U V. Okay, so that's the algorithm. So, if I were to take a look at this uh example graph over here, maybe A is my start vertex. I initialize it to uh This is not a DAG. Thank you. Let's make it a DAG. I claim to you now this is a DAG. Okay? In particular, a topological sort order is when there's a path through all the vertices, then there's a unique topological sort order. A B E F G H D C. This is a topological order. You can check all the vertices the edges.

So, I'm going to start with a uh by setting the uh actually let's use E. Let's do shortest paths from E. Why not? Okay? Shortest paths from E. Vertex A actually comes before E in the topological order, right? So, it has no I mean, its shortest path distance when I initialize, I'm going to initialize this to zero. I'm going to initialize this to infinite infinite infinite Infinite. All these things to infinite. These are my estimates. These are not quite the shortest paths yet. Distances. But when I get here, clearly I can't be distance to me being infinite can never violate the triangle inequality with something infinite or finite.

Doesn't matter. Right? So, I don't do anything to A. Anything before my source vertex in the topological order can't be visited, right? Because it's before in the topological order. That's That's the kind of the point. There's no path from my source vertex to anything before it in the topological order. Okay? So, same with B. B is before it in the topological order. Okay? Now, I'm at E. And it's possible we are violating triangle inequality. In particular here, right? I think the shortest path distance to F is infinite, but actually if I go to E through this edge with a weight three, I know that this is violating triangle inequality.

So, actually this thing is wrong and I can set it equal to three. Okay? Now, that might not be the shortest path distance, but right now it's a better estimate. Right? So, we've set it. Okay. Now, I'm moving on. I'm done with this guy. I move to the next vertex in my topological order, and again I relax the edges out of F. Okay, so here, looking at eight, 3 + 8 is better than infinite. So, we'll say that that's 11. And 3 + 2 is better than infinite, so that's 5. Okay? Now, I keep going in the topological order. G is the next. 5 + 1 is 6. Okay, so we found a better estimate here. Right? So, this 11 is not as good.

6 is better, so we replace it. Here, we haven't visited before. It's still infinite, so 5 + - 2 is 3. Okay? This is the next in the topological order. 3 + 9 is bigger than 6, so that's not a shorter path. 3 + 4 is certainly smaller than infinite, so set that equal to 7. Then 7 + 5 is also bigger than 6. And actually, if you can you can confirm that these are all the shortest path distances from E. Okay? So, this algorithm seems to work. Does it actually work? Let's take a look. The claim to you is that at the end of relaxation this algorithm we've set claim at end uh all the estimates equal shortest path distances.

Okay? The basic idea here is that if I take uh a the kth vertex in the topological order assuming that these distances are all equal for the ones before me in the topological order, I can prove by induction. Right? We can consider a shortest path from S to V, right? The Kth vertex. And look at the vertex preceding me along the shortest path, right? That that vertex better be uh before me in the topological order or we're not a DAG, right? And we've already set its shortest path distance to be equal to the correct thing by induction. So, then when we processed U, right? S to U to V. When we processed U in DAG relaxation here, processed the vertex, and looked at all its outgoing adjacencies, we would have relaxed this edge to be no greater than that shortest path distance.

So, this is correct. You can also think of it as the DAG relaxation algorithm for each vertex looks solid at its incoming neighbors, assuming that their shortest path distances are computed correctly already, right? Any shortest path distance to me needs to be composed of a shortest path distance to one of my incoming neighbors through an edge to me. So, I can just check all of them. That's what DAG relaxation kind of does. And again, we're looping over every vertex and looking at its adjacencies, doing constant work. This again takes linear time. Okay, so that's shortest paths in a DAG. Next time we'll look at for general graphs how we can use kind of the same technique in a algorithm we call Bellman-Ford.

Okay, that's it for today.

Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

11. Weighted Shortest Paths