I think we know that there are no negative cycles because we couldn't relax any more edges starting from the 6th iteration, if we could relax any more after the (n-1)th iteration then that should signal a negative cycle.
Really enjoyed your explanation.. thanks.. but I have a doubt. we know an important property of Bellman-Ford algorithm is that at i th iteration (i=1,2,3,4,..) we find shortest path of i hop length or less for each node in the graph. Your explanation worked finetill iteration 3. In iteration 4, we should find shortest path of hop length 4 or less to each node. We can not find the path S-A-E-B-C-F path from S to F which is hop length 5. I think that, after updating path for C (S-A-E-B-C) at 4th iteration updating path for F should have been done in next iteration. Please let me know your thoughts. thanks.
I have been taught this in a different way. In class, we don't consider iterations. We consider hubs/jumps instead. In a sense that in iteration 1, we are allowed to do 1 jump, in iteration 2, we are allowed to do 2 jumps and etc. Let's say that, in your graph, G and H have path to each other. That is G has path to H and H has path to G. Now in iteration 3, with 3 jumps,we can have the following paths S->A->E->H or S->A->E->G yet we cannot have S->A->E->G->H or S->A->E->H->G until iteration 4, in which we are able to make 4 jumps I'm not sure but I think your way works on 1-way directed graphs not in both-ways graphs. Please correct me if I'm wrong
+TheAddictioneer I learned algorithms from the Cormen Lieserson Rivest and Stein (CLRS) algorithms book, which is widely considered the Bible on algorithms (although it's not very readable). Many of my videos are based on pseudocode from CLRS, and I hope my videos are far easier to understand than reading the CLRS textbook. I realize there are many variations to algorithms, and a variety of ways to implement them. My way may not always be the best way. Thanks for sharing your experience. Since my videos are geared towards teaching I try to keep my code as simple as possible. For this video, my algorithm will work on both directed and undirected graphs, but not on graphs with negative weight cycles.
Thank you for showing the predecessor (pi) list. All other examples of this algo just show how to calculate the distances - but nothing about the actual path - which is the whole point. So, it's like, I know the shortest distance, but what exactly is the shortest path? Thanks for clearing that up.
Shouldn't you be looking for negative cycles before you start the BF algorithm? In this example you stopped when the distances converged, but if you have a negative cycle you'll keep going to infinity and therefore never get to the final verification step. Am I missing anything here?
During Iteration #3, we can also consider the edge weights of G-D and H-G as we've found their distances. Is that right? Or do we need to wait for the next iteration?
+Aagam Shah No, in iteration 3 you can only consider outbound edges from A, B and E. You can't consider edges out of G and H yet because the costs to get to G and H are still infinity at that point.
Joe James Yes, correct. But as we consider the outbound edges of E, we get the distance for G. I was confused because in further iterations, you've updated the outgoing edges and used their distances in the same iteration. I'm sorry, I'm not able to put my point across effectively. Hope you understand my dilemma. Thank you.
+Aagam Shah you're right! Thanks for catching that. I had to watch it 3 times to see it. In iteration 3 we relax edges EH and EG, so we should also consider outbound edges from G and H because they are alphabetically after E. So I'll have to post a correction when I get time.
Dexter Aparicio some of the node distances may happen to be correct if a negative cycle is found anywhere in the graph, but the algorithm does not identify which, if any distances are correct and which are not. I only knows that a negative cycle will cause some of the distances to be wrong, so it declares the whole solution invalid.
Best explanation of Bellman-Ford.
Awesome Samantha Tite Webber !
I think we know that there are no negative cycles because we couldn't relax any more edges starting from the 6th iteration, if we could relax any more after the (n-1)th iteration then that should signal a negative cycle.
Good job man!
Really enjoyed your explanation.. thanks.. but I have a doubt. we know an important property of Bellman-Ford algorithm is that at i th iteration (i=1,2,3,4,..) we find shortest path of i hop length or less for each node in the graph. Your explanation worked finetill iteration 3. In iteration 4, we should find shortest path of hop length 4 or less to each node. We can not find the path S-A-E-B-C-F path from S to F which is hop length 5. I think that, after updating path for C (S-A-E-B-C) at 4th iteration updating path for F should have been done in next iteration. Please let me know your thoughts. thanks.
best explanation. also helpful for understanding time complexity in a simple manner.
Shouldn't we go from G to D in iteration 3??
D is at infinity and G is at 5.
Am I right or am I missing something?
I have been taught this in a different way. In class, we don't consider iterations. We consider hubs/jumps instead. In a sense that in iteration 1, we are allowed to do 1 jump, in iteration 2, we are allowed to do 2 jumps and etc.
Let's say that, in your graph, G and H have path to each other. That is G has path to H and H has path to G. Now in iteration 3, with 3 jumps,we can have the following paths
S->A->E->H
or S->A->E->G
yet we cannot have S->A->E->G->H or S->A->E->H->G until iteration 4, in which we are able to make 4 jumps
I'm not sure but I think your way works on 1-way directed graphs not in both-ways graphs. Please correct me if I'm wrong
+TheAddictioneer I learned algorithms from the Cormen Lieserson Rivest and Stein (CLRS) algorithms book, which is widely considered the Bible on algorithms (although it's not very readable). Many of my videos are based on pseudocode from CLRS, and I hope my videos are far easier to understand than reading the CLRS textbook. I realize there are many variations to algorithms, and a variety of ways to implement them. My way may not always be the best way. Thanks for sharing your experience. Since my videos are geared towards teaching I try to keep my code as simple as possible.
For this video, my algorithm will work on both directed and undirected graphs, but not on graphs with negative weight cycles.
Thank you for showing the predecessor (pi) list. All other examples of this algo just show how to calculate the distances - but nothing about the actual path - which is the whole point. So, it's like, I know the shortest distance, but what exactly is the shortest path? Thanks for clearing that up.
Shouldn't you be looking for negative cycles before you start the BF algorithm? In this example you stopped when the distances converged, but if you have a negative cycle you'll keep going to infinity and therefore never get to the final verification step. Am I missing anything here?
+hazegirl18 no. You check for negative cycles last. The algorithm stops after |V| -1 iterations, so it will never continue endlessly.
Clear explanation. Thanks.
do you have a source code for this? badly needed
excellent video :)
During Iteration #3, we can also consider the edge weights of G-D and H-G as we've found their distances. Is that right? Or do we need to wait for the next iteration?
+Aagam Shah No, in iteration 3 you can only consider outbound edges from A, B and E. You can't consider edges out of G and H yet because the costs to get to G and H are still infinity at that point.
Joe James
Yes, correct. But as we consider the outbound edges of E, we get the distance for G.
I was confused because in further iterations, you've updated the outgoing edges and used their distances in the same iteration.
I'm sorry, I'm not able to put my point across effectively. Hope you understand my dilemma. Thank you.
+Aagam Shah you're right! Thanks for catching that. I had to watch it 3 times to see it. In iteration 3 we relax edges EH and EG, so we should also consider outbound edges from G and H because they are alphabetically after E. So I'll have to post a correction when I get time.
in iteration 2 you can go from E to B ,G,H ...
if there is a 'negative cycle', is the entire solution path to the other nodes outside and far from this negative cycle becomes invalid also?
Dexter Aparicio some of the node distances may happen to be correct if a negative cycle is found anywhere in the graph, but the algorithm does not identify which, if any distances are correct and which are not. I only knows that a negative cycle will cause some of the distances to be wrong, so it declares the whole solution invalid.
excelent =)