Bellman-Ford in 4 minutes — Theory

Показать описание

The theory behind the Bellman-Ford algorithm and how it differs from Dijkstra's algorithm.

Рекомендации по теме

Комментарии

Its so hard to find concise but useful videos like this. Extremely useful for last minute revision.

DrTryloByte

got an exam on algorithms in two days. Your channel has helped me out a bunch throughout the semester, thank you!

owenmajor

It's basically a dp, you iterate v-1 times, first time 1 length edge, second time 2 length edge path, until v-1 length edge path, this is the most important part. You should mention this

yangmyfly

Please keep making videos, they're excellent.

ryancross

Thumbs up for showing difference between Dijkstra and Bellman-Ford in case of negative edge! :D

DeepanshuThakuriamgsak

At ~1:22, you say using Dijkstra would make it so no more updates could be done on the path to A. But if you ignore the input constraint saying no edge has a negative weight and you apply Dijkstra's anyways, it would actually work in this example.
Distance to A is 3 after updating from S. When we start checking the edges of B, we check its edge to A and see it is -2. Distance S -> B = 4. And 4+(-2)=2, which is less than the distance S -> A = 3. So now the shortest distance to A is correctly labeled as 2.

skateboarddude

Better explained than what I can pick up from a class! Nice explanation on why we need a max of V-1 iterations

danielyang

You are very articulate and the videos are well prepared.

UmairAkhtar

1:34 if we Dijkstra normaly, wouldn't we get the same result as Bellman-Ford? ? I mean you can't just close it after only 1 iteration bc Dijkstra visit all vertices, not stop when just only reach vertex A.

walterclementsjr.

Great videos :D. One correction @2:38. A Simple path is a path that has no repeating vertices (this condition includes no repeating edges as well). The statement that all paths are simple still stands.

thesvodnik