Bellman Ford Algorithm | Shortest path & Negative cycles | Graph Theory

Bellman Ford algorithm explanation video on how to find the shortest path and handle negative cycles.
Github source code link:
github.com/williamfiset/algor...
=================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on KZbin:
www.udemy.com/course/graph-th...

[@kevintran6102]

We need to run V-1 times because we run edges in random order so we could run from the vertex has positive infinity cost to another vertex also has positive infinity cost. So we could reduce time complexity if we run edges in an order that assures unvisited vertex will be visited from visited vertex, right?

[@WilliamFiset-videos]

Only in the worst case does it take V-1 iterations for the Bellman-Ford algorithm to complete. Another stopping condition is when we're unable to relax an edge, this means we have reached the optimal solution early. In practice, this optimization works very well from tests I've conducted in the past. See here for an example: github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordEdgeList.java#L42

[@amanthapliyal2636]

But if we maintain that order isn't it kind of Dijkstra's then!

[@jerryleeio]

@@amanthapliyal2636 that's what I was thinking. Bellman ford can be built on top of Dijkstra

[@ecpgieicg]

@@amanthapliyal2636 Nope. Dijkstra is a greedy algorithm, which only produces the correct result in the absence of negative edges. Bellman-Ford searches for all paths of lengths |V|-1 (and uses another round to detect negative cycles.) They are different. Their proofs of correctness are different. Their implementations are different. (imo, both VERY different) You can't equate the two by pointing to identical results for a strict subset of total valid inputs.

[@ecpgieicg]

@@WilliamFiset-videos Thank you for the vid and for sharing. For what I can tell, the early stop condition works because path length with respect to the source vertex can exceed |V|-1 before |V|-1 rounds of edge relaxation depending on the ordering of edges chosen. If we were to choose valid edges in each round based on distance from source vertex, as if keeping track of level sets like in Breath-First Search, I'd expect that exactly |V|-1 rounds of edge relaxations are still required -- albeit we'd also perform a lot less number of relaxations each round. Otherwise, I'd expect to be able to construct counter examples (the easy ones would be with a negative weight edge) .

[@nmamano]

To elaborate on why we do "V-1" iterations, it comes from the following lemma: "if the shortest path from the source to a node v ends with the edge u->v, and we already know the correct distance to u, and then we relax the edge u->v, we will find the correct distance to v". It is a pretty obvious lemma, if you think about it, but the correctness of Bellman-Ford, Dijkstra, and topological sort are all based on it. The consequence of this lemma is that, in order to find the correct distance to a node v, we need to relax all the edges in the shortest path from the source to v *IN ORDER*. Dijkstra and topological sort are efficient because we only relax the out-going edges from each node after we found the correct distance for that node, so we only need to relax the edges once. Unfortunately, the combination of cycles and negative edges makes it impossible to find a "good" order to relax the edges. Thus, Bellman-Ford just relaxes all the edges in an arbitrary order (this is one iteration of Bellman-Ford). In the first iteration, we find the correct distance for all the nodes whose shortest paths from the source have 1 edge. In the next iteration, we find the correct distances for all the nodes whose shortest paths from the source have 2 edges, and so on. If the shortest path with the most edges has k edges, we need k iterations of Bellman Ford. Of course, we do not know what "k" is in advance, but, since shortest paths never repeat nodes (assuming there are no negative cycles), what we know for sure is that any shortest path will have at most V-1 edges (in the case where it goes through every node). This is why V-1 iterations is ALWAYS enough, but often not necessary. If in one iteration of Bellman-Ford no relaxation yields any improvement, it means that we already found all shortest paths and we can finish.

[@mohits94]

Loved the explanation! Thanks

[@user-ls5pd3xn4h]

Good explanation. Thank you.

[@vivekpal1004]

Thanks. Do you have any reference for this?

[@ryankang562]

Wow, okay that was amazingly intuitive and well explained. Props to you man

[@mylifemyvines6689]

i am satisfied with this explanation !thanks alot

[@arvindroshaan3335]

Simpler way to understand why we need V-1 iterations: Consider a graph 0->1->2->3 (linearly connected) and the source is 0 and let all the edge weights be 1. Since order of edge updates is random, let's consider the worst case. So for iteration 1, we update the edge 0->1 at last (as it the only edge that relaxes, i.e only edge whose processing reduces the distance to a node). For iteration 2, we update 1->2 edge at the end and similarly iteration 3, update 2->3 at the end At start: d = [0,inf,inf,inf] After Iter0: d = [0,1,inf,inf] After Iter1: d = [0,1,2,inf] After Iter2: d = [0,1,2,3] As you can see, it takes in the worst case V-1 (here 4-1=3) iterations to propogate the edge weights. This just shows that we atleast require V-1 updates in the worst case. But can we show that V-1 iterations is sufficient for getting optimal distances from the source? I would like to here from you, if you had managed to read till the end!

[@nozawatakahiro7730]

I filled the gap in my knowledge. Thanks for your great works, William.

[@eduardotorres8684]

Well done! Great explanation of Bellman-Ford!! Loved the animation.

[@FavoriteCentaurMoe]

One of the quickest and simplest explanations properly

[@guyfawkes9720]

Great pacing! It was difficult for me to get so appreciate the correctness and calmth in speech

[@anjaybruss]

your animation clears up the concept so much !

[@adanjsuarez]

Great video, and thank you for the Github repository!

[@YasasCPerera]

Absolutely great videos. Thank you very much.

[@aleksandr-belousov_1]

Wow, man, you have a terrific repository with algorithms =)

[@hamzasabri5610]

thx man way to go wish best of luck keep going bro

[@dotproduct763]

Quality content! worth every second 👌

[@mrdragos7151]

Damn, this video made it very easy to understand! Thank you!

[@pipilu3055]

do we need another E*V loop to find all nodes that have negative infinity value? How about find all those nodes which are further reduced in the first round of your second loop and then do a DFS from those nodes? Or do I miss anything?

[@demodemo252]

Thank you for making this video. Easy to understand

[@ben-kd9dr]

Thanks very much. From what you showed, we detect vertices that are either part of a negative cycle or reachable through a negative cycle. How can I find all these (simple) negative cycles or at least the one with the smallest weight? Thanks very much again!

Thank you for explanation. In the section that we check negative cycles, i think there should be one iteration for all edges so the result is not coincidence.

[@stepanberan4641]

There should be O(V-1) iterations of this relaxation checking because the algorithm is dependent on the order of edges.

[@JEETUKUMAR-jm7ft]

Thanks for the Github Repo!

[@valeriaveraherrera7587]

in min 5:48 at the bottom of the pseudocode you say that D[edge.to] = -inf in case of a negative cycle, however by only doing this the distance from 0 to 1 in your previous example would be -2 instead of -inf, for which we think it would be necessary to also do D[edge.from] = -inf. This or I messed up when writing my code lol

[@rainbi991]

My professor in class taught the use cases this way: Djikstra's: not guaranteed to work when there are negative edges Bellman-Ford: will not give the correct answer if there is a negative cycle but works with negative edges Any negative cycle: the answer is always -infinity as you can just go through the negative cycle infinitely for an infinitely short distance So before solving any shortest path problem, you can check all edges for negative values, and run a dfs for cycle detection and check if the cycle edges sum up to a negative value to figure out what case you're in

[@codewithbug]

hey thanks for that! it really helps me :)

[@qzz8873]

good video,learned a lot.thanks

[@alexanderkuptsov6117]

3:48 Is there a typo on the slide? I guess the rightmost vertex should be 6, right?

[@orangeshoes]

Thank you for this video! You're awesome :))

[@kaikewesleyreis]

Thanks a lot for your video. Basically you help me to solve a Foobar Challenge! Best regards from brazil :D

[@MrWuggles]

You're doing God's work my man.

[@pedroenriquealfonsopita5192]

I think you only need a pass through the edges to check if any can be relaxed in order to find a negative cycle. Why are you looping through each vertex in the negative cycle detection code?

[@avihooilan5373]

Dijkstra doesn't loop infinitely when there are negative edges... it simply won't give you the correct result (since it doesn't take into account negative cycles). It does however find the minimal simple paths (paths with no cycles) even when there are negative edges.

[@WilliamFiset-videos]

Umm that does sound fishy. I'm not sure what I was thinking then so you're probably correct. Thanks!

[@rinkiyakepapa2420]

Dijkstra won't necessarily give the correct minimal path when there are negative edges (even WITHOUT NEGATIVE CYCLES). Consider the case where the cost from node A to B is 3, A to C is 2 and B to C is -4. The trio doesn't form a negative cycle but once C has been updated to a minimum distance of 2 from A, it won't be relaxed further even when the distance through B might lead to a cost of -1 since C has already been visited before B reached out to it. This reflects the greedy property of Dijkstra in comparison to Bellman-Ford's dynamic programming.

[@kidze31]

Hi, what about printing out 1 negative sequence?

[@lucianosaldivia5917]

Is there a way to distinguish between nodes DIRECTLY in the negative cycle vs loops REACHABLE by the negative cycle?

[@ahmetkarakartal9563]

YOU SAVED MY LIFE

[@sneh9817]

Thanks a lot. Negative cycles *sigh*

[@felixmunzlinger9388]

isn't it that in iteration 9 #4 has to be put to 55 and #9 to 155 since (-20)+75 is 55

[@xxozmozxx]

i always watch your videos before sleep.

[@smarahadi6155]

that's weird

[@alexanderkuptsov6117]

Is this supposed to be a compliment?

[@hasanulislam3112]

How can we modify the bellman ford algorithm so that it can find the shortest path if there is a negative weight cycle?

[@marlieemam216]

for checking a negative cycle, we only need one pass through all edges and not [ V - 1] passes

[@migzleon4047]

Can't wait to become a patreon...

[@ron0studios]

what happens if there are multiple edges leading into a single node?

[@prasannathapa1024]

Do we need to Iterate V-1 Times again in the 2nd phase of BF algo? (where you updated values to -ve infinity)?

[@asifsaad5827]

i don't think so! it seems awkward as he did so! everywhere I have read or seen, they did not do such thing 'V-1' times!

[@prasannathapa1024]

@@asifsaad5827 No we need to actually I tried and found it needs to be spread

[@asifsaad5827]

@@prasannathapa1024 so we have to iterate again V-1 times?

[@prasannathapa1024]

@@asifsaad5827 Yes!

[@asifsaad5827]

@@prasannathapa1024 6 months later and my exams are already over >-

[@TheFernandinator]

There's a little fault in the animation of Bellman ford at 9:40 - distance of node 4 isn't 60, because distance of node 2 is -20 and -20+75 = 55 which is better

[@TheFernandinator]

and therefore distance of node 9 isn't 160 but 155

[@mathuratudu7271]

great videos.. Can you please make videos on max flow algorithms

[@WilliamFiset-videos]

Mathura Tudu thanks! Network flow is on my todo list. Sometime in the near future I hope :)

[@emzy888]

I don't think that simply relaxing the edges in the second iteration of BF that you run is sufficient to detect edges reachable from a negative cycle. You can construct a graph that requires more than (V - 1) trips through the negative weight cycle before you are able to relax an edge reachable from the cycle. So, you will certainly find the nodes involved in a cycle by relaxing edges, but further modifications are necessary to find nodes reachable from the cycle.

[@terakonapie3856]

What does "relax" exactly mean in this algorithm ? I barely speak english (for this topic) and this expression is overwelming difficult to understand for me. I also speak german and russian if maybe somebody could translate it suitable

[@glenneric1]

Can't you fix the negative cycle problem by finding the lowest path weight and biasing all of the paths up by that amount? In this case just add 2 to every path.

[@pepehimovic3135]

10:09 is a mistake right? Adding 10 is certainly not obtaining a “better” value

[@navjotsingh9801]

what if graph is not connected...so we should run bellman ford for each unvisited node...right?

[@caiodavi9829]

then the distance is infinity (cant reach)

[@bantix9902]

you can actually accelerate this, by cutting off early if I remember correctly, but I'd have to look it up again

[@samjacob7300]

9:12 Why does node 3 change from a value of 35 to 30?

[@shirleyfong7329]

i was wondering the same thing

[@codewithbug]

I think this is because the weight of 2 is 20, and when we go to 3, we add +10, so we have 30, which is less than 35

[@hemanthchalla4833]

nice.

[@Robert4865]

Is there something like negative infinity in C or C++?

[@vishalmishra7018]

INT_MIN

[@ajitshiva3282]

memset(dist, 128, sizeof(dist));

[@caiodavi9829]

@@vishalmishra7018dont use this. it is prone to overflow

[@yash1152]

3:58 dislike for lower audio volume levels, like for good visuals & explanation.

[@forthehomies7043]

9:11 Why does Node 3 cost drop to 30?

[@lucianosaldivia5917]

Node 2 had a cost of 20, if you add the +10 of the edge 2->3, you get 30

[@vyorkin]

how to find all negative cycles?

[@tarunkrishna1564]

Number of vertices should be 8 instead 9 as there is no "Node 8".

[@sasanktadepalli1231]

Sir, how to find the path along with distance?

[@sams.3224]

I find the part for edge in graph.edges unnecessarily cryptic and verbose: for v in graph.v { for u in graph.adjacent[v] { relax(u, v, dist, weights); } } seems more reasonable notation for understand the inner workings.

[@d36247]

can you give me slides please ?

[@rickmonarch4552]

1) Most books say that if the bellmann ford detects a negative cycle, then it just returns false. 2) U said nothing about saving or reading the path from the result. 3) Didn't note, that it works with negative edges only if there is no negative cycle they create.

[@adityavikramsinha408]

Damn

[@nimaghasemi7058]

Are you good homie?

[@jothi1018]

"risk-free geans""