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
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.
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!
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.
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.
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
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
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!
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?
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.
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 :)
Well done! Great explanation of Bellman-Ford!! Loved the animation.
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 filled the gap in my knowledge. Thanks for your great works, William.
One of the quickest and simplest explanations properly
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!
Great video, and thank you for the Github repository!
Great pacing! It was difficult for me to get so appreciate the correctness and calmth in speech
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 =)
i always watch your videos before sleep.
that's weird
Is this supposed to be a compliment?
lol
10:09 is a mistake right? Adding 10 is certainly not obtaining a “better” value
You're doing God's work my man.
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.
for checking a negative cycle, we only need one pass through all edges and not [ V - 1] passes
YOU SAVED MY LIFE
Damn, this video made it very easy to understand! Thank you!
thx man way to go wish best of luck keep going bro
Thank you for making this video.
Easy to understand
Is there a way to distinguish between nodes DIRECTLY in the negative cycle vs loops REACHABLE by the negative cycle?
Thanks a lot. Negative cycles *sigh*
Thanks a lot for your video. Basically you help me to solve a Foobar Challenge!
Best regards from brazil :D
3:48
Is there a typo on the slide? I guess the rightmost vertex should be 6, right?
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
Absolutely great videos. Thank you very much.
Can't wait to become a patreon...
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
Thanks for the Github Repo!
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?
Quality content! worth every second 👌
good video,learned a lot.thanks
Thank you for this video! You're awesome :))
3:58 dislike for lower audio volume levels, like for good visuals & explanation.
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!
you can actually accelerate this, by cutting off early if I remember correctly, but I'd have to look it up again
isn't it that in iteration 9 #4 has to be put to 55 and #9 to 155 since (-20)+75 is 55
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 >-
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
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
How can we modify the bellman ford algorithm so that it can find the shortest path if there is a negative weight 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)
how to find all negative cycles?
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?
what happens if there are multiple edges leading into a single node?
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.
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.
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?
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.
Number of vertices should be 8 instead 9 as there is no "Node 8".
Sir, how to find the path along with distance?
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
can you give me slides please ?
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.
Damn
"risk-free geans""
Are you good homie?