Bellman Ford Algorithm | Shortest path & Negative cycles | Graph Theory

Bellman Ford algorithm explanation video on how to find the shortest path and handle negative cycles.

Github source code link:

=================================

Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on YouTube:

[kevintran]

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?

[nmamano]

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.

[rainbi]

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

[FavoriteCentaurMoe]

One of the quickest and simplest explanations properly

[eduardotorres]

Well done! Great explanation of Bellman-Ford!! Loved the animation.

[nozawatakahiro]

I filled the gap in my knowledge. Thanks for your great works, William.

[guyfawkes]

Great pacing! It was difficult for me to get so appreciate the correctness and calmth in speech

[avihooilan]

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.

[MrWuggles]

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.

[anjaybruss]

your animation clears up the concept so much !

[DavidDLee]

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.

[xxozmozxx]

i always watch your videos before sleep.

[adanjsuarez]

Great video, and thank you for the Github repository!

[aleksandr-belousov_]

Wow, man, you have a terrific repository with algorithms =)

[marlieemam]

for checking a negative cycle, we only need one pass through all edges and not [ V - 1] passes

[lucianosaldivia]

Is there a way to distinguish between nodes DIRECTLY in the negative cycle vs loops REACHABLE by the negative cycle?

[migzleon]

Can't wait to become a patreon...

[mrdragos]

Damn, this video made it very easy to understand! Thank you!

[samjacob]

9:12 Why does node 3 change from a value of 35 to 30?