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?
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 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.
@@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) .
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.
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
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.
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.
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
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
Damn, this video made it very easy to understand! Thank you!
4 ปีที่แล้ว +1
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.
Very clearly explained. You need V-1 times in the worst case. However, if in a round there were no relaxations performed, obviously the next round will also not have any too, so you can stop by detecting the number of relaxations made in a round to be zero.
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?
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!
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.
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?
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.
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
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.
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.
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?
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
But if we maintain that order isn't it kind of Dijkstra's then!
@@amanthapliyal2636 that's what I was thinking. Bellman ford can be built on top of Dijkstra
@@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.
@@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) .
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.
Loved the explanation! Thanks
Good explanation. Thank you.
Thanks. Do you have any reference for this?
Wow, okay that was amazingly intuitive and well explained. Props to you man
i am satisfied with this explanation !thanks alot
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
hey thanks for that! it really helps me :)
this is the BEST video explaining bellman-ford, pretty helpful
Well done! Great explanation of Bellman-Ford!! Loved the animation.
I filled the gap in my knowledge. Thanks for your great works, William.
9:11 Why does Node 3 cost drop to 30?
Node 2 had a cost of 20, if you add the +10 of the edge 2->3, you get 30
10:09 is a mistake right? Adding 10 is certainly not obtaining a “better” value
Here d[2] + 10 = -20 + 10 = -10, which is better than d[3] which is -5, so we update it. Similarly we do for the other nodes.
One of the quickest and simplest explanations properly
9:12 Why does node 3 change from a value of 35 to 30?
i was wondering the same thing
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
Great pacing! It was difficult for me to get so appreciate the correctness and calmth in speech
Great video, and thank you for the Github repository!
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.
Umm that does sound fishy. I'm not sure what I was thinking then so you're probably correct. Thanks!
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.
your animation clears up the concept so much !
Wow, man, you have a terrific repository with algorithms =)
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
and therefore distance of node 9 isn't 160 but 155
i always watch your videos before sleep.
that's weird
Is this supposed to be a compliment?
lol
You're doing God's work my man.
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
3:48
Is there a typo on the slide? I guess the rightmost vertex should be 6, right?
Damn, this video made it very easy to understand! Thank you!
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.
There should be O(V-1) iterations of this relaxation checking because the algorithm is dependent on the order of edges.
thx man way to go wish best of luck keep going bro
Great video! Thanks.
Thank you for making this video.
Easy to understand
Very clearly explained.
You need V-1 times in the worst case. However, if in a round there were no relaxations performed, obviously the next round will also not have any too, so you can stop by detecting the number of relaxations made in a round to be zero.
Absolutely great videos. Thank you very much.
Quality content! worth every second 👌
Thanks for the Github Repo!
YOU SAVED MY LIFE
good video,learned a lot.thanks
for checking a negative cycle, we only need one pass through all edges and not [ V - 1] passes
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?
Thanks a lot. Negative cycles *sigh*
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!
Thanks a lot for your video. Basically you help me to solve a Foobar Challenge!
Best regards from brazil :D
Thank you for this video! You're awesome :))
Thanks a lot
3:58 dislike for lower audio volume levels, like for good visuals & explanation.
Do we need to Iterate V-1 Times again in the 2nd phase of BF algo? (where you updated values to -ve infinity)?
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!
@@asifsaad5827 No we need to actually I tried and found it needs to be spread
@@prasannathapa1024 so we have to iterate again V-1 times?
@@asifsaad5827 Yes!
@@prasannathapa1024 6 months later and my exams are already over >-
Is there a way to distinguish between nodes DIRECTLY in the negative cycle vs loops REACHABLE by the negative cycle?
what if graph is not connected...so we should run bellman ford for each unvisited node...right?
then the distance is infinity (cant reach)
isn't it that in iteration 9 #4 has to be put to 55 and #9 to 155 since (-20)+75 is 55
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.
How can we modify the bellman ford algorithm so that it can find the shortest path if there is a negative weight cycle?
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?
great videos.. Can you please make videos on max flow algorithms
Mathura Tudu thanks! Network flow is on my todo list. Sometime in the near future I hope :)
Hi, what about printing out 1 negative sequence?
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.
what happens if there are multiple edges leading into a single node?
Is there something like negative infinity in C or C++?
INT_MIN
memset(dist, 128, sizeof(dist));
@@vishalmishra7018dont use this. it is prone to overflow
how to find all negative cycles?
Number of vertices should be 8 instead 9 as there is no "Node 8".
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
nice.
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.
Sir, how to find the path along with distance?
can you give me slides please ?
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.
Are you good homie?
Anagram for "Behemoth" and "Baphomet" two very vicious and very violent Djinns. Peace Next
you can actually accelerate this, by cutting off early if I remember correctly, but I'd have to look it up again
Damn
"risk-free geans""