Shortest PathLesson 37Free preview

DSA Bellman-Ford

This lesson is part of DSA · All levels

Summary

Bellman-Ford is looking for the shortest path from one source and able to handle the negative side of the rot. The algorithm does a whole-sided relaxation of V-1 times, then an additional spin to detect a negative cycle. Its complexity makes it slower than Dijkstra, but more flexible.

Key points

Dealing with the negative side as long as there is no negative cycle
Relax all sides as much as V-1 times
The last round is used to detect negative cycles.
Complexity

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.