# 12. Bellman-Ford

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=f9cVS_URPc0
**Transcript page:** https://www.withtranscript.ai/video/f9cVS_URPc0

## Chapters

- 0:12 — Chapter 1 (0:12)
- 4:01 — Chapter 2 (4:01)
- 6:08 — Chapter 3 (6:08)
- 10:49 — Chapter 4 (10:49)
- 14:25 — Chapter 5 (14:25)
- 18:16 — Chapter 6 (18:16)
- 20:30 — Chapter 7 (20:30)
- 22:28 — Chapter 8 (22:28)
- 28:41 — Chapter 9 (28:41)
- 31:44 — Chapter 10 (31:44)
- 33:07 — Chapter 11 (33:07)
- 34:57 — Chapter 12 (34:57)
- 38:26 — Chapter 13 (38:26)
- 42:00 — Chapter 14 (42:00)
- 45:00 — Chapter 15 (45:00)
- 46:40 — Chapter 16 (46:40)
- 48:28 — Chapter 17 (48:28)
- 51:37 — Chapter 18 (51:37)
- 55:03 — Chapter 19 (55:03)

## Transcript

**[0:12]:** Okay, let's get started. Welcome to the 12th lecture of 6.006. This is our second lecture talking about weighted graphs and in particular weighted shortest paths algorithms. Last time we talked about weighted graphs. This is a kind of a generalization of what we mean by distance in an unweighted graph instead of each edge having a weight of one essentially. Right? We generalize that to be any integer. And last time we we showed how to solve shortest single source shortest paths in a graph that doesn't have cycles even if it has zero or negative weights in linear time using an algorithm called dag relaxation. We also showed in that lecture how in linear time if we are given the shortest path weights to all the things reachable in finite or with shortest path distance that's finite, we can construct a shortest paths tree from those weights in linear time.

**[1:19]:** Okay? So, this is motivating why we're not really going to talk about parent pointers for the next couple of lectures. We're just going to concentrate on these shortest path weights. Right? And so today we're going to be talking about our most general algorithm we'll be showing for solving single source shortest paths. In particular in graphs that could contain cycles and could have negative weights. Okay? So, just to recap uh our little road map here. Uh single source shortest paths in linear time. Last time we discussed another linear time algorithm dag relaxation. And today we're going to be talking about Bellman-Ford which isn't limited to acyclic graphs. In particular there could be negative weight cycles in our graph. Right? If it has cycles and has negative weights, the worry is that we could have negative weight cycles. In which case there is if if a negative weight cycle is reachable from our source then the vertices in that cycle and anything reachable from that cycle will potentially have an uh an unbounded number of edges you need

**[2:33]:** to go through. There's not a bound on the number of edges for a shortest path because I could just keep going around that cycle as many times as I want and get a shorter path, right? And so we assign those distances to be minus infinity. Okay? So, that's what we're going to do today in Bellman-Ford. In particular, what we're going to do is compute our shortest path distances, these shortest path weights for every vertex in our graph setting the ones that are not reachable to infinity and the ones that are reachable through a negative weight cycle to minus infinity and all other ones we're going to set to a finite weight. And another thing that we might want is if there's a negative weight cycle in the graph let's return one. Okay? So, those are the two kinds of things that we're trying to solve in today's lecture.

**[3:28]:** Okay? But before we do that, let's warm up with two short exercises. The first one exercise one Okay? Given an undirected graph given undirected

**[3:53]:** graph G

**[4:01]:** return whether

**[4:07]:** G contains a negative weight cycle.

**[4:20]:** Anyone have an idea of how we can solve this in linear time actually? In fact, we can do it in order E. Uh no. Yes. Yes, reachable from S. I guess let's just say if a negative weight cycle at all. Not in the context of single source shortest paths. Check whether there's a negative weight edge. Ah. Your colleague has determined uh an interesting fact about undirected graphs. If you have a a negative weight edge in an undirected graph, I can just move back and forth along that edge. That's a cycle of length two or I guess three vertices back back to where we came from that is of negative weight because I'm just traversing that weight over and over and over again. So, the question of single source shortest paths of finding negative weights is not particularly interesting in the undirected case. What I can do is just for every negative weight edge undirected edge in my graph, I can just you know, find the reachability from the vertices the end points of that edge and label them as minus minus delta.

**[5:40]:** Basically, if the connected component containing S has a negative weight edge, then everything in the graph is accessible from a negative weight cycle. So, this is not such an interesting problem and so we're going to restrict our discussion today

**[5:58]:** today to directed graphs.

**[6:08]:** Uh so, this is uh if and only if exists negative weight edge. Okay? Okay, exercise two. Kind of a little preview for what's to come. We're actually not going to show you an algorithm directly that meets this Bellman-Ford running time V times E. What instead we're going to show you is a an algorithm that solves single source shortest paths in so, given an algorithm alg A solves single source shortest paths in order V times V plus E time. Okay, what is that? That's V squared plus V times E. Right? That's close to what this V times E is. Okay? That's what we're going to show you. But if I had such an algorithm can anyone tell me a single source shortest paths how we can use this algorithm to solve single source shortest paths in V just V times E time? Okay?

**[7:35]:** Show how to solve SSSP in order V times E. I guess we can put a a dot there as well. Okay? So, this is a little tricky. It's kind of related to the difference we had between the reachability problem and the single source shortest paths problem that we saw last lecture, right? This When are these asymptotically different in their upper bound is when V is asymptotically larger than E. Right? But the connected component containing S can have at most E vertices or order E. It it can actually have at most E plus one vertices because uh otherwise it wouldn't be connected. Okay? So, what we can do if we had such an algorithm we could first when we're given our graph explore everything in the graph using BFS or DFS, find all the things reachable from S and then just throw away everything else. Now I have a graph for which V is asymptotically no bigger than E.

**[8:58]:** And then we can use this algorithm to solve single source shortest paths in V times E time. Okay? I'm not going to write all that down here. You can see it in the notes. Yeah. Does this work if your graph isn't simple? Does this work if your graph isn't simple? I haven't thought about it. We are not going to talk about non-simple graphs in this class. Uh but probably not because you've got a lot of edges. Though in our class if we're talking about single source shortest paths, if we have multiple edges between two vertices, we can just take the minimum weight one because it's never better to take the larger ones. Did that answer your question? Great. All right. So, those are our warm-ups. That's our goal. We need to find an algorithm for single source shortest paths in general graphs, graphs with potentially graphs with cycles and negative weights.

**[9:49]:** And solve it in this V times linear kind of time. That makes sense? All right. So, first before we get to the algorithm, we're going to take uh discuss a little bit about simple short about shortest paths in general. If we didn't have The problem here is negative weights. How do we find if we had negative weight cycles, there seems to be these problems because we could have minus infinities in our deltas. But if we didn't have negative weights, I'd like to assert to you that our shortest paths, even if there are negative weights, are going to be simple. They won't repeat vertices. So, that's the first thing we're going to show you. Uh Find that uh let's say simple shortest paths.

**[10:49]:** Okay. So, claim. I'm going to give my claims numbers today just because I'm going to have a lot of them. If my shortest path distance from S to some vertex is finite, meaning it's not infinite or minus infinite, right? Some finite value. There exists

**[11:20]:** a shortest path. A shortest S to V path that is simple. And remember, simple means not going through a vertex more than once. All right. How are we going to prove this?

**[11:49]:** Well, consider if this claim was not true, right? If every shortest path contains a cycle, essentially, right? It it it repeated a vertex. Then my path looks something like this.

**[12:11]:** I mean, there's some vertices along here, and then I go to V. So, here's S, and then there's this some cycle I repeat some vertex. I'm going to call this cycle at C. Okay? Now, what do I know about this path? I know that it has it's a shortest path, and it has finite weight, right? So, in particular, this path, this delta distance, is not minus infinity. But if this is not minus infinity, what do I know about the weight of this cycle?

**[12:49]:** Yeah, it can't be negative, right? Cuz if it was negative, I could keep going around this cycle, and this would have a non-finite weight, shortest path distance from S, right? So, I know this is you know, can't be negative, so it must be zero or positive, right? But if it's zero or positive, and this is a shortest path, right? Went through this cycle, then I could remove it. And now, I have a new path with one fewer cycle. I could just keep doing this to create a simple path. Okay? So, that checks out. Okay. So, that's interesting. If it's simple, what do we know about the number of edges in a simple shortest paths? How many could there possibly be? How long in number of edges could a simple shortest path path be? If I can't repeat vertices, right? I can have at most V vertices on my simple path, which means I can use at most V minus one edges, right?

**[14:04]:** Fence posting, right? So, simple paths have at most V minus one edges.

**[14:25]:** That's a nice little thing I'd like to to box off. That's a really nice property, right? So, while uh a shortest path here could have an infinite number of edges, right? If the shortest path distance is finite, I know I only have to check paths that use up to V minus one edges. In particular, this is finitely bounded in terms of the number of paths I have to consider. It's exponential potentially, right? But at least it's finite. Okay? The other The other way I I potentially had to check every possible path, of which there could be infinite if there's cycles in my graph. Okay. So, I have an idea. Okay? What if I could find shortest path distances by limiting the number of edges I go through, right? So, not the the the full shortest path distance from S to V, but let's limit the number of edges I'm allowed to go through, and let's talk about those shortest path distances, just among the paths that have at

**[15:45]:** most a certain number of edges. I'm going to call this uh K edge distance. And I'm just going to provide a little notation here. Instead of having a delta, I'll have a delta K here. That That means how many edges I'm limited by, okay? So, from S to V is shortest uh S to V path using at most K edges.

**[16:29]:** Short weight. Weight of a shortest path shortest S to V path using at most K edges, okay? And the these notions seem somewhat symmetric, right? If I were able to compute this thing for V minus one, right? Then it for all the vertices, then if the distance is finite, then I'll have successfully computed the real shortest paths because of this statement, right? Now, that doesn't mean that if it's if this is uh it doesn't mean the other way, right? If this is minus infinity, right? If the shortest path distance is minus infinity, it doesn't say anything about what this is, right? It just says the shortest path using at most V minus one vertices using it at most V minus one edges uh would be whatever this is. But really, the shortest path length needs to consider an infinite number of edges, right? So, it doesn't really tell us much about that.

**[17:49]:** But for the finite ones, it does. It works well. And so, if we are able to compute this thing for K equals V minus one, in a graph that doesn't contain negative weight cycles, we'd be done, right?

**[18:06]:** I claim to you a stronger statement that if

**[18:16]:** the shortest path using at most V edges from S to V is less than strictly less than delta of V minus one,

**[18:33]:** right? This is all in the subscript here, right? Basically, this is the shortest path distance of any simple path, right? And possibly ones that also contain cycles, but definitely it includes all the the simple paths, right? If there's a shorter path to my vertex that goes through more than V minus one edges, that this path can't be simple, right? Cuz it goes through a vertex more than once. Otherwise, it would be included in this distance set, right? So, if this is the case, and I have found a shorter path to V that uses V edges uh yeah, that uses V edges, that path can't be simple, which means that path or some path there contains a negative weight cycle. Okay? So, if this is true, then I know that the real shortest path distance from S to V must be minus infinity.

**[19:48]:** Right? I'm going to call such a vertex a witness, right? If if we can find a vertex that has this property. I mean, I haven't shown you how to compute these things yet, right? But, if I were able to find a vertex V and these are capital V's if you uh having trouble. These this V is different than this V. This is cardinality, right? If we can find such a vertex V that certifies that there is a negative weight cycle in our graph. So, I'm going to call V is a witness.

**[20:30]:** Okay. So,

**[20:36]:** if this property is true, it's a witness and it definitely has this. Is it possible, you think? I'm going to claim to you that it's possible that a vertex could have minus infinite distance, but not have this property hold. Okay? There's I could probably give you an example. I don't have one off the top of my head right now, but that's possible. You could imagine there might be no path going to a vertex on a negative weight cycle that goes through V exactly V edges, right? It might go through more edges, a shorter one, right? So, this equation would be an equality and would not certify that this is true, right? But, I claim to you if a vertex has this property, if it's re- its shortest path distance is minus infinite, then it must be reachable from a witness, okay? So, that's the claim.

**[21:40]:** If delta S V is minus infinity,

**[21:50]:** then V is reachable from a witness. Reachable from a vertex that has this property, that has this property. And if it's reachable from something that has minus infinity shortest path weight, then I can take that path, go to my reachable vertex, and that's also minus infinite path, right? Okay. So, how do we prove this?

**[22:28]:** Well, let's consider

**[22:36]:** Let's Let's I'm going to state a somewhat stronger statement uh that we'll prove instead. Okay? It suffices to prove that every negative weight cycle contains a witness. If we were to prove that, right? Then every vertex with this property, every vertex with this property has uh is reachable from a negative weight cycle by definition. Okay? So, if we can prove that every

**[23:18]:** prove every

**[23:24]:** negative weight weight cycle contains

**[23:36]:** witness. Right? If we can prove that every negative weight cycle contains a witness, then every vertex reachable from one of those witnesses, in particular reachable from a negative weight cycle,

**[23:53]:** has is uh has shortest path distance minus infinity, and that should prove the claim, right? Uh is This thing has to be reachable from a negative weight cycle.

**[24:10]:** Uh And so, if we prove negative weight cycles contain witnesses, then all of these vertices are reachable from a witness. Okay, great. Great. Confusing myself there for a second. Okay. So, let's consider a negative weight cycle in G, okay? This is a directed negative weight cycle. Recall. Okay? This is be my negative weight cycle C, right? All of the sum of the edges in this thing, the wei- the weights has negative weight. And I'm going to have a little bit notation. If I have a vertex V here, I'm going to say that its predecessor in the cycle, I'm just going to call it V prime. Okay? That's just some notation. All right. So, if I have computed these shortest path distances to every vertex in my graph, shortest path distance going through at most V vertices and the shortest path distance going through at most V minus one vertices, then I know

**[25:25]:** the following thing holds. Delta of V going from S to V for any vertex in my cycle can't be bigger than delta V minus one from S to U plus the weight, sorry, not U, V prime, its predecessor, plus the weight going from the predecessor to my vertex. Why is that? Why is that? Because this is the weight of some vertex uh this is the weight the shortest path distance to my predecessor using one fewer edge. And so, this in particular is the weight of some path that uses V edges. So, if this is the shortest such path distance, this has to upper bound it, right? At at least at most, yeah. Is that the triangle inequality? That's that is a statement of the triangle inequality. Thank you. All right. So, Yes, this is just by triangle inequality. Okay. Now, what we can say is let's take this equation summed over all vertices in my cycle, okay?

**[26:46]:** So, I'm just going to add su- uh summation here of all vertices in my cycle of this whole thing. Okay? I'm going to do that out a little bit neater, okay? Summation of del- delta, not D, delta V S V.

**[27:15]:** I guess I don't need this open parentheses. Equals or less than or equal to sum of V in C of delta V minus one uh V prime. Okay? And here I'm summing over V in C, and this is just my notation for it's the predecessor, right? And then I'm going to sum over the weights in my cycle. V in C, right? These are just some of the weights in my cycle. Well, what do I know about this cycle? Right? This is just the weight of C, right? Weight of C. That's awful handwriting. C. What do I know about the weight of the cycle? It's negative, right? So, this is less than zero, which means that if I remove this, this needs to be a strict equality, right? But, if this if the sum of all of these is less strictly less than the sum of all these, we can't have none of the vertices in my graph satisfying not satisfying this property, right?

**[28:41]:** Right? If all of them are not witnesses, then this thing is bigger than this thing at least as big as this thing for every vertex in my cycle, which is a contradiction, right? So, the claim holds if we have a negative infinite shortest path distance, then V is reachable from a witness. So, it suffices for us to find all the witnesses, find all the vertices reachable from the witnesses, and then mark them as minus infinity. Does that make sense? Okay. So, now we finally are able to get to our algorithm. All right. Bellman-Ford.

**[29:31]:** And what I'm going to show you today is a little different than what is normally presented as Bellman-Ford. The original Bellman-Ford algorithm does something a little different, and because it does something a little different, which we'll talk about at the end. It's a little hairier to analyze. I'm going to show you a modification that is a little easier to analyze and has this nice property that we're going to be able to use the algorithm to give us a negative weight cycle if it exists. Okay? So, we're going to say this is a maybe a modified Bellman-Ford. And the idea here is to

**[30:17]:** make a vertex associated make many versions of a vertex. Okay? And I want this version of the vertex to correspond to whether I came here using zero edges, one edge, two edges, three edges. I have a different vertex version of the vertex for each one of these uh for for uh uh a path going through at most a certain number of edges. Okay? So, this is an idea called graph duplication. Idea. Graph duplication. And this is a very common technique for solving graph-related problems because essentially what I get to do is I get to store information, right? It's I'm I'm I'm I'm if I'm having different versions of a vertex, I can have that vertex correspond to reaching that vertex in a different state. Okay? So, that's what we're going to do here. The idea here is make

**[31:30]:** V plus one levels. Basically, duplicate vertices in our graph

**[31:44]:** where vertex VK in level K

**[31:55]:** represents reaching

**[32:03]:** vertex V using at most K edges. Okay? So, this definition seems similar to what we're doing up here, right? If if we have vertices that have this property, then their shortest paths in this new graph might correspond to these K edge distances. And really what the name of the game here is to compute these two for every vertex because then we can com- then if uh D is finite, delta is finite, then this guy will be the length of our shortest path. And if they're different, that'll be a witness and we can explore from it. Okay? So, and if uh we connect

**[33:02]:** edges

**[33:07]:** uh from one level to only higher levels,

**[33:22]:** basically levels with a higher K, then this graph is going to be a DAG.

**[33:34]:** OH, THAT'S COOL. WHY IS THAT COOL? Because we saw how to solve single-source shortest paths in a DAG in linear time. Now, this graph that we're going to construct is going to have V plus one levels, so could have our our graph kind of explodes V times, right? We're going to do that in a second. I'm going to be more precise with what I mean there. But if we're multiplying our graph V V plus one times, then the size of our graph is now V times larger. That doesn't That's not so hard to believe, but if we made our graph V times larger and we ran a shortest path algorithm in linear time with respect to that graph, then that graph has something like size V times V plus E size.

**[34:37]:** That looks familiar, maybe?

**[34:42]:** That's this running time, right? So, if we can find an algorithm that runs in that running time, we can get down to V times E. Okay? So, let's try to do that.

**[34:57]:** Here's the transformation I'm going to show you. I'm going to show you first with an example. Okay? Here's an example of a directed graph that does contain a negative weight cycle. Okay? Can anyone find it for me?

**[35:16]:** B C D, right? Has weight minus four plus three minus one. It has a minus two total weight, right? So, that's a negative weight cycle. Okay? So, if I were to take shortest paths from A, right? I will want to say at the end of my algorithm, this better be zero. And all of these better be minus infinity, right? So, that's what I want in my in my algorithm. So, what's my algorithm going to be? I'm going to make V plus one copies of this graph and I'm going to kind of stretch it out, right? Okay. So, here I have V 0 1 2 3 4. There are four vertices in my graph. So, this is 1 2 3 4 5 copies of my graph. I have a version of vertex A for each one of those copies, a version of vertex B for each of those copies, C and D, etc.

**[36:17]:** Okay? So, I have this nice grid of vertices. And I'm not going to put any edges within a layer, within a level, right? Because then I mean, this graph has cycles, right? And I don't want cycles in my graph, right? What I'm going to do instead is for every edge in my original graph, for example, the edge from A to B, I'm going to connect it to the the B in the next level, right? So, A0 is connected to B1 with an edge weight of minus five, just like in the original. Okay? And I'm going to do that for every edge in my graph and I repeat that down all the way. Okay? In addition, I'm going to add a zero weight edge from A0 to A1 or from every vertex all the way down the line. These are all zero weight edges corresponding to I'm not going to traverse an edge.

**[37:13]:** I'm just going to stay at this vertex. Okay? That's going to allow us to simulate this at most K edges condition. Now, if you take a look at paths in this graph from A0, our starting vertex,

**[37:31]:** clearly none of the other vertices are in that level are reachable from A0, right? Just as we want, right? Because the shortest path distance to any of these vertices using at most zero edges should be infinite, right? I can't get there in zero edges. Okay? But then any path in this graph using at most uh uh K edges is going to correspond to a path from zero A0 to a vertex in that level, the corresponding level. So, for example, if I had a uh if I was looking for paths to B, right?

**[38:26]:** Using at most three edges, right? Any path a a path from A0 to B3 in this graph would correspond to a path in this graph that uses at most three edges, right? So, let's find such a path. Okay? So, going to from A0, B1, stay at B1, stay at B, sorry. Yeah, that's a that's a path using fewer than three edges or at most three edges. Okay? But there's another path here. Where is it? Going from A A A to B. Okay, that's not such an interesting one. That's the same path. So, I might have more than one path in here corresponding to a path in there, but my claim is that any path in here corresponds to a path in here. Okay? So, what's a what's a path of length three that's non-trivial? Yeah, A to C to D to B. Okay? So, A to C to D to B.

**[39:42]:** Yeah, that that's a path, right? And I basically because I constructed this so that the edges always move from level to level, as I traverse these edges, I always change levels. Yeah. But my original graph doesn't have these self loops with with zero weight. yes. My original graph doesn't have an edge from A to A. That's true. Right? I'm using these edges to correspond to I'm deciding not to take an edge, right?

**[40:19]:** It's not that I'm like doing any work here. I'm just staying there for a state. Okay? And that's what's going to allow me to get this at most edges. All right. So, this is the graph we construct. Hopefully, you understand that we made these uh V layers, right? This is V. Right? And a vertex we made V copies of every vertex and connected them using edges in this way. Okay. So, first step of Bellman-Ford is construct this graph.

**[40:57]:** Uh So, Bellman-Ford construct construct G prime as described above. It has how many vertices?

**[41:16]:** V * V + 1, right? V * V + 1 vertices. And how many edges? Well, I have one edge for outgoing edge for each vertex corresponding to just staying in the same place, right? So, that's V squared vertices, I mean edges. And then I have one edge for every edge in my graph. I have K Sorry, I have uh V - 1 Sorry, just V. I have V edges for every edge in my graph. Okay? So, that means So, this is the number of vertices.

**[42:00]:** And V * V + V * E. This is V V + E. All right, cool. So, that's how many edges I have. So, we constructed it in that way. It's a DAG, right? If we only have edges going to increasing levels, then this thing can't have cycles because otherwise that would mean there would be an edge pointing backwards, right? And we didn't construct any of those. All right. So, we construct this graph G prime. We can do that in linear time with respect to these things. I just go through all the edges, I make these edges and I make these vertices. It's It doesn't take anything. I just do it naively, right? I can do that in time V * V + E asymptotically. Okay. Now, I run DAG relaxation our nice algorithm we had last time from in there it was A0. I'm going to say it's S0, our source our source vertex single source shortest paths.

**[43:27]:** So, that I compute

**[43:33]:** delta of S0 to VK for all K in what is it? 0 to V. Right? That's what single source shortest paths does, right? It computes for me this distance from my source at some source, right? To every other vertex in the graph. And so, in particular, I get these, right? Well, that that is all of them. Then for each vertex V set the thing I'm going to return uh D value uh S to V equal to the shortest path distance I got from DAG relaxation to a particular vertex. Uh V V - 1. All right? Why do my Why am I doing this? Right? I'm setting it to be the shortest path distance to the guy in the second to last row here or column

**[45:00]:** in my modified graph.

**[45:05]:** The hope is that this distance in my DAG corresponds to

**[45:18]:** this distance in my original graph, right? Uh the distance to V using at most V - 1 edges, right? So, that's the claim That's the claim we're going to prove in just a second. I'm going to write it down just so that we have just to continue our train of thought. Claim

**[45:40]:** delta S0 VK equals delta K the K edge distance from S to V.

**[45:55]:** That's That's what we want to claim. That would then What would that mean then? That would mean that I'm correctly setting the shortest path distance here for all vertices whose distance is finite. Great. I mean I I set values to things where they're not finite and where they're minus infinity also. But in particular, I set the ones correctly if they're uh finite. Okay. So, the last thing we need to do is deal with these minus infinity vertices, right? But we know how to do that, right? We just look at the witnesses because we've computed this value

**[46:40]:** for K = V and K = V - 1. And if that claim over there is true then those shortest path distances are the same as these K edge shortest path distances. And we can just for every vertex, we compare these things. If this is satisfied, we got a witness. Right? Okay. So, for

**[47:14]:** each witness

**[47:20]:** U in V you know, where delta S0 U V is less than strictly S0 U V - 1. That's the definition of a witness here. Close the parentheses. Then for each vertex V reachable from U set del- uh sorry, D. D is what we're returning. D of S V equal to minus infinity. So, that's the end of the algorithm. Basically, I'm looking for all the witnesses. For each witness, I find all of the vertices reachable from it and set it to minus infinity just as we argued before. Okay. So, it remains to prove this claim.

**[48:28]:** How do we prove this claim? Well, we can induct on K, right? Is this true for K = 0? Yeah, right? We kind of already argued it over here when we were talking about our initialization step or what what DAG relaxation does. It'll set this to be the shortest path from this guy to all of these vertices. These aren't reachable from here, and so these are infinite. And that one's zero. Okay? So, the base case So, induct on K.

**[49:11]:** Base case, K = 0, check, right? That's all good. Now, we induct our inductive step. Let's take a look at the shortest path distance from zero from S0 to V of K prime for some K prime. And the assumption is the inductive hypothesis is that this distance is the K edge distance for all K prime less than K I mean all K less than K prime, right? Well, kind of by definition of a shortest path this is the minimum over all incoming vertices of the shortest path from S zero to U of K prime minus one plus the weight of the edge of the edge from U of K prime minus one to V K prime for all U K prime minus one in the adjacencies the incoming adjacencies of V K prime. Okay, what does this mean? Right? I'm just saying in my graph G prime a shortest path to this vertex needs to go first through some uh vertex in the layer before it which is one of these.

**[50:44]:** And in particular I'm only connected to things uh adjacent to me. That's all this is saying, right? I have to go through that vertex and take some shortest path to one of those previous vertices. Now, in actuality these adjacencies I constructed them to be similar to the adjacencies in my original graph. In addition to one edge coming from my original vertex, right? From from vertex V. So, this is the same as the minimum of this set delta S naught same thing

**[51:26]:** plus W U V for all uh

**[51:37]:** U in the adjacent incoming adjacencies of my original vertex in addition to one more term. What is that other term?

**[51:54]:** These are all of the things corresponding to my incoming edges in my original thing, but I also have that one edge coming from the V before it, right? So, this is I'm going to union union union this with delta S naught V of K prime minus one. Awful. I think there's another one here. This is S naught V of K prime minus one. Okay? I'm not going to rewrite it. Okay.

**[52:34]:** Then by induction this thing and this thing must be the edge shortest paths using K minus one vertices and then that's just the statement of what the shortest path should be using at most K prime edges going from S to V. Okay? So these things are the same as we claimed. Yay, check. All right, and then it's not such a trivial it's it's kind of a trivial leap then to say that at the end of Bellman-Ford these guys uh sorry, the things that we return these guys are the shortest path distances because here if they're finite we set them to their true shortest path distance and if they're minus infinity that invariant means that these things correspond to exactly this claim over here.

**[53:44]:** It's a witness.

**[53:49]:** And then finding all the vertices reachable from those witnesses we set all of the infinite ones to be minus infinity as desired. Okay, so what's the running time of this thing? Well, we had to construct this graph, so we had to take that time. Okay? We ran DAG relaxation. That takes the same amount of time. Right? For every vertex we did O order V work. And then for each witness, how many could there be? At most V. Checking the reachability of each vertex, that can be done in how long? Order E time. Right? Cuz we don't need to consider the things that aren't connected to X or aren't connected to the witness. Right? So, this thing takes order V times E work. So, we're upper bounded by this the a time it took to construct the original graph and by the claim we had before that takes V times E time.

**[54:52]:** Okay. So, that's Bellman-Ford. I'm just going to leave you with two nuggets.

**[55:03]:** First, the shortest uh shortest path

**[55:10]:** if for any witness, let's say we have a witness here. Do I have any witnesses here? Uh I didn't construct I didn't fill in all these. But is there a vertex on this cycle that goes through uh who has a shortest path that goes through four vertices that's smaller than any other, right? Okay, I can go from A to C to B to D to B to C. And you can work out this algorithm. I have it in the notes that you can take a look at. This will actually have a shorter path for vertex, sorry. It'll have a shorter path for vertex B.

**[56:01]:** A to B to C to D to B. Thank you. That's a path of length four of four of edges. That has shorter path than any path that has fewer edges. In particular, there's only one other path to B using fewer than four uh there's two other paths. One path of length uh that has one edge that has weight minus five and one path this path that has weight nine minus one is eight. Right? Whereas this path minus five minus four three minus one has minus 10 plus three is minus seven which is shorter than minus five. So B indeed is a witness, right? And if we actually take a look at that path through this graph going from A to B to C to D back to B

**[57:03]:** we see that there's a negative weight cycle in this graph. B to C to D to B. And indeed that's always the case for our witnesses. Okay? You can see a proof of that in the notes and you can see in recitation a little space optimization to make us not have to construct this entire graph on the fly, but actually only use order V space while we're going. Okay, so that's Bellman-Ford. Sorry for running a little late.
