Bellman-Ford in 4 minutes - Theory 

Yeah that's exactly the nature of this algorithm.

+Ryan Cross Glad you like them!

more no of edges also means parallel paths

Unfortunately, he stopped uploading short after this video.

Thank you; I agree.

Ah, I'm sorry! Hopefully this code clears it up: github.com/msambol/youtube/blob/master/shortest_path/bellman_ford.py

I agree I still caonfuse why Dijkstra can not do it

Negative edges are allowed but not negative cycles. Otherwise you can relax the nodes indefinitely. See code here: github.com/msambol/dsa/blob/master/shortest_path/bellman_ford.py

did u ?

did u ?

@@Leo-io4bq yupppp

See here for working code: github.com/msambol/dsa/blob/master/shortest_path/bellman_ford.py

Unfortunately, he stopped uploading short after this video.

supdawg Revisit the example where they're all in a straight line. Because we do |V| - 1 iterations, we pass through every node on our way to D. If we did |V| iterations, we'd have to pass through a node twice, aka a cycle. If the cycle was positive we wouldn't include it on our path anyway. Remember we can't have negative cycles. Hopefully that helps. Let me know if you're still having trouble.

supdawg I think you understand that a path with |V| edges is impossible. So if we iterate |V| - 1 times, we would find the path that has |V| - 1 edges, if that was indeed the shortest path.

Michael Sambol I guess a way to rephrase my question would be, why wouldn't the algorithm just compute the shortest path after the first iteration? What do the iterations after the first do for the algorithm? I understand that the graph may not be completely sorted out after only the first iteration, but why is that the case?

supdawg Hmm, maybe watch this video: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-obWXjtg0L64.html. You'll see we're not done after the first iteration.

Michael Sambol Everything up to about 2:40 makes perfect sense, but I get lost after when you jump to saying "we know if we iterate |V| - 1 times, we're guaranteed to find the shortest path from s to d". I think what doesn't make sense to me is we aren't iterating over one edge per iteration, we are iterating over all the edges per iteration in |V| - 1, so why wouldn't one iteration work? As in, per iteration, we are updating every edge, so if we have n iterations, we are updating each edge n times. Why do we update each edge n times? Why can't we update each edge just once?

Glad I could help. Thanks for watching. :)

Unfortunately, he stopped uploading short after this video.

Welcome!