The Bellman Ford Algorithm Visualized

A free video tutorial from Loony Corn
An ex-Google, Stanford and Flipkart team
Rating: 4.3 out of 5Instructor rating
67 courses
165,833 students
The Bellman Ford Algorithm Visualized

Lecture description

Visualize how the Bellman Ford works to find the shortest path in a graph with negative weighted edges.

Learn more from the full course

From 0 to 1: Data Structures & Algorithms in Java

Learn so you can see it with your eyes closed

14:58:54 of on-demand video • Updated April 2019

Visualise - really vividly imagine - the common data structures, and the algorithms applied to them
Pick the correct tool for the job - correctly identify which data structure or algorithm makes sense in a particular situation
Calculate the time and space complexity of code - really understand the nuances of the performance aspects of code
English [Auto]
That was an introduction to the Belmond phone algorithm. Now we look at how it actually works. So we are now going to run the Belmond Ford algorithm on this graph, note that it has negativities edges the first initialize the distance dbl, just like we always do. So there is an entry for every vertex in the distance table and the initial distance of all the vertices is infinite. To start running the Belmond for the algorithm, we can choose any vertex at random, since this algorithm covers all the edges in the graph V minus one things, we can essentially start with anybody else and we'll get the exact same result. So in order to find the shortest path between any two vertices, you can start the calculation of the shortest path and feeling the distance debris from a neat vortex. Remember that you just choose a vortex at random. For the first iteration, we start with word excel at random. We start with what XP and explore all its neighbors. The first Neba that we explore is what X be the distance of B is the distance of a little bit of edge E, comma B, and as you can see, the distance of B will be two to start off with. The distance of E is zero because that's the source. Now let's explore the edges of B, the distance of B, if the distance of B plus the rate of edge B comedy be get five. Remember, the important thing here is not exploding the vertices, but exploring the edges. Make sure you cover every edge. That's the important point here. Let's not look at the edge from B to it has a negative beep, so the distance of E is the distance of B that is still minus two. That is the negative bit of edge to E, which means the distance of what X? E is zero. Explore the edge now from E to B, which has an edge rate of one B is already present in our distance table with a distance of five. However, the new distance is smaller than five. So we basically update the distance table with the new distance, which is equal to the distance of E, plus the weight of the edge E would be equal to one. The next edge we'll explore is the edge from E to see it's still unexplored and the distance to see will be one. The distance from E is zero and the edge is one. What other unexplored edges? The one from free to be so the distance to it can be calculated as the distance of C plus the weight of the edge C, E, which is one plus two equals two three. However, E already has a distance of zero associated with it. Three is greater than zero. So we ignore three and do not update the distance of E. And finally, we explore the last edge in the first iteration, back from C to be the distance of B, if you sum it up through C, if one minus five, which is equal to minus four, minus four is smaller than the distance that were existed at B, equal to two earlier. So we replaced two with minus four. After the first iteration, the distance table will look something like this. This is the distance table after the first iteration in our Bellmon Ford algorithm there are in place for everybody and the distance to that vertex is specified in the distance, Diebel as well. Notice something about the distance to everybody. You'll see that the distance two vertices, B and C are accurate. Distances with which are at one edge distance from the source that we've chosen are accurate, the remaining distances are not accurate and we need further iterations to get accurate distances for the remaining purposes. So once more, we go to the next iteration and apply. And calculate new distances to input into the distance table. Once again, we start from E to be. The distance is, too, and since two is bigger than the distance already available to be, we simply ignore it. So we ignore to and leave the distance of B as minus four. Let's explore the next edge. The next edge goes from B to the vortex. B, the distance to B is now minus four. We have a newly updated distance to be so the distance to be will be minus four plus three, which is equal to minus one. So that's the new distance of the vertex B. Let's go on and explore the next edge between B and E here. Once again, we have a new distance to be is minus four and the edge between B and C is minus two, which gives us a new distance of minus six. The next edge that we explore is between E and B, minus six, plus one. Gives us a new distance for the yet again, so minus one we can get rid of and the new distance study is minus six. Plus one equals two. Minus five. Other ideas to explore between and see we have the right distance so we can move on. Then between C and E. The distance now from eight to see to eat is three, but we already have a better distance to eat, that is minus six so we can ignore three since three is greater than minus six. We finally explored the last edge between C and B once again. This distance is minus four. We already have updated beat with the correct value, minus four. So we are done. We explored all the edges once more in the second iteration. After exploring all the distances, all the edges, we update the distance dbl with the new values. So there it is, here we have the distance debris after the second iteration of relaxing all the edges in this graph. If you notice now, the distance to every vertex is accurate. After this separation, all distances are accurate. It so happened that we got accurate distances for all vortices from Source E with just two iterations. It's the graph is set up such that this was possible, however, for the Belmond, for an algorithm to work on any graph we have to find to guarantee that we find the shortest path in any graph we need V minus one iterations. We've mentioned this earlier and now will logically see why V minus one iterations unmetered. Now, the longest possible spot in a graph of vertices has V minus one edges. This is when the graph is one long line of vertices. You have an edge connecting every vertex. So four vertices if you have V minus one edges. This is the longest possible path in a graph. After one iteration, all vertices, which are one edge away from the solar vortex that you've chosen, are accurate, this makes sense because we have to exhaustively explore all edges to get the correct, accurate distance for every word. In one iteration, we would have explored thoroughly all edges, which are all vortices, which are one distance away from the source edge and the distance for those adjacent vortices, which are one edge of it, will be accurate. After two iterations, all vertices, which are two edges away from the source vertex, are accurate. That's because we would have successfully explored all parts which are the edges away from the source. So all parts which lead to these two edges of it would have been explored. We will have accurate information, distance information for those vortices. And after three iterations, all vertices which are at a distance of three edges away from the source, will have accurate distance information associated with it so that every iteration we have accurate distance information forward to sees that many number of edges away from the source. Which means if you do V minus one iterations, we can guarantee that the vortex, which is furthest away from the source, will have its distance accurately calculated. Because this guarantee only exists at the V minus one iteration, we need at least V minus one iterations for the Belmond Ford algorithm to give accurate results.