Graph Theory37 sections · 1633 units
Open in Course

LeetCode 787 Cheapest Flights Within K Stops - Lessons

(summary)

Bellman-Ford can handle constrained path problems by controlling the number of iterations. Each iteration extends paths by one edge, letting you enforce maximum path length. Two-array relaxation prevents mixing path lengths within a single iteration. This is temporal separation: reading from the previous state and writing to the current state keeps each iteration independent.

This technique generalizes to any problem where you need shortest paths with at most kk edges. The number of iterations directly controls the maximum path length.