The Bellman Ford Algorithm Visualized

Loony Corn
A free video tutorial from Loony Corn
An ex-Google, Stanford and Flipkart team
4.2 instructor rating • 73 courses • 129,047 students

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 Belman for a lot of them. Now we look at how it actually looks. So we are now going to run the Belman for algorithm on this graph. Note that it has negative written edges. The first initialize the distance people just like we always do. So there is an entry for every vertex in the distance table and the initial distance of all the world to see is if infinite to start running the Belman for all that and then we can choose any vertex at random. Since this algorithm covers all the edges in the graph we minus one fames. You can essentially start with any word X and we get the exact same result. So in order to find the sharpest part would any to vertices you can start the calculation of the shortest part and feeling the distance deeply from a neat vertex remember that you just choose the word X at random for the first iteration. We start with word X at random Izaak with Vortex A and explore all its neighbors. The first number that we explore is what X be the distance of B is the distance of B plus the rate of edge the MIB. And as you can see the distance of B will be to start off at the distance of is zero because that's the source. Now let's explore the edges of B the distance of B is the distance of B plus the bit of edge B.Com might be to get five. And remember the important thing here is not excluding the vertices but exploring the edges. Make sure you cover up every edge. That's the important point here. Let's not look at the edge from B. It has a negative b. So the distance of E is the distance of B that is to minus two. That is the negative bit of edge Eat Eat which means the distance of what X eat is zero. Exclude the edge now from E. B which has an edge rate of 1 B is already present in our distance table at a distance of five. However the new distance is smaller than 5. So we basically update the distance D-B with the new distance which is equal to the distance of plus the read of the edge enough to be equal to one the next edge will explore the edge from easy to see. It's still unexplored. And the distance you see will be one the distance from it is zero. And the edge rate is one. What other unexplored edges. The one from see to eat. So the distance to eat can be calculated as the distance of. That's the leap of the edge Seacom East which is one plus two equals to three. However he already has a distance of zero associated with it three is greater than zero. So we ignore the and do not be the distance of each. 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 is one minus five which is equal to minus four minus four is smaller than the distance that were existed at be equal to two. Earlier so we replaced you with minus four after the first iteration. The distance Deeble will look something like this. This is the distance. After the first iteration in Belman forward again. There are entries for everybody x and the distance to that where X is specified in the distance the blast way notice something about the distance of the books you'll see that the distance over the CS B and C are accurate distances with which are at the one edge distance from the source that we've chosen are accurate the remaining distances are not accurate and we need for the iterations to get accurate distances for the remaining what this is. So once more we go through the next iteration and apply and calculate new distances the input into the distance table. Once again we start from it to be that distance is 2 and since 2 is bigger than the distance already available to be we simply ignore it. So we ignore you and leave the distance of B as minus 4. Let's explore the next edge the next edge goes from B to the vertex be the distance to B is now minus four. We have a newly upgraded distance to be so the distance to B B B minus four plus three which is equal to minus 1. So that's the new distance of the vortex. B let's go on and explore the next edge between B and eat here. Once again we have a new distance to eat. B is minus four. And the edge between B is minus two which gives us a new distance of minus 6. The next edge that we explore is between E and B minus 6 plus 1 gives us a new distance for the yet again. So minus 1 we can get rid of the distance to be minus 6 plus one equals minus five. Other ages to explore between ency we have the right distance so we can move one then between C and E the distance now from 8 to eat is three. But we already have a better distance to eat. That is minus 6. So we can ignore 3 since 3 is greater than minus 6 finally explore the lost edge between C and B once again this distance is minus four. We already have a B and B with the correct value minus four. So we are that we've explored all the edges once more in the second iteration. After exploring all the distances all the edges the obvious the distance table that the new values. So that it is here we have the distance table after the second iteration of relaxing all the edges in this graph. If you notice now the distance to every about X is accurate. After this deletion or distances are accurate it so happened that we got accurate distances for all vertices from source a. With just two editions. It's the graph is set up such that this was possible. However for the Belman for 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 1 iterations. We'd mentioned this earlier. And now we logically see Vyvian minus 1 iterations are needed. Now the longest possible part in a graph of the vertices has the minus 1 edges. This is when the graph is one long line of thought to see if you have an edge connecting every word x. So we vote to see if we have B minus one. Just this is the longest possible path in a graph after one iteration all vertices which are one edge of B from the source vertex that the chosen are accurate. This makes sense because we have to exhaustively explore all edges to get the correct accurate distance for every one takes in one iteration. We would have explored pettily all edges which are all good to see which are one distance away from the source edge and the distance for those adjacent four deceased which are one edge of it would 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 two edges away from the source. So all parts which lead to were to cease to exist or we 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 we'll have accurate distance information associated with it. So at every iteration we have accurate distance information forward to seize that many number of edges away from the source. Which means if you do a B minus or one in the oceans we can guarantee that the word X which is far away from the source will have its distance accurately calculated because this Garantie only exists at the V minus one iteration. We need at least a B minus 1 iterations for the Belman for algorithm to give accurate results.