Sign in to watch this lesson
Advanced - Graphs · 5:00
Bellman–Ford & SPFA
Bellman–Ford finds shortest paths when some edges are negative by relaxing every edge of an edge list in up to n − 1 phases: after phase i, every vertex whose shortest path has at most i edges is final, and a phase that changes nothing ends the run early. One more phase that still relaxes reveals a negative cycle reachable from the source, which we print by walking n parent steps first. SPFA re-checks only the vertices whose label just dropped, which is fast on typical graphs but still O(nm) in the worst case.
You will learn
- Run Bellman–Ford over an edge list and explain why n − 1 phases suffice: after phase i, every vertex whose shortest path has at most i edges has its final label
- Write the relaxation with the d[a] < INF guard, the early exit when a phase changes nothing, and a −INF clamp
- Detect a negative cycle reachable from the source with an n-th phase, and print it by taking n parent steps before collecting the loop
- Implement SPFA with an in-queue flag and enqueue counts, and explain why its worst case is still O(nm)