Graph Theory37 sections · 1633 units
Open in Course

Section Recap

(What you learned)

You learned why Dijkstra fails with negative edges and how Bellman-Ford solves this by relaxing all edges n1n-1 times. Each iteration extends shortest paths by one edge. You saw how to detect negative cycles using an nn-th iteration and how to find affected nodes using reachability checks.

You solved problems involving maximum paths, cycle extraction, and constrained shortest paths. Bellman-Ford is slower than Dijkstra but handles cases Dijkstra cannot: negative weights and cycle detection. Knowing when to use each algorithm is a core skill in graph algorithms.