Pattern visualizer

Cheapest Flights Within K Stops

The catch is not cheapest price alone — Dijkstra would lock in the direct 500 flight as final the moment it is the smallest tentative distance, and never look back once a cheaper-but-longer route needs one more flight than it has already used. Bellman-Ford sidesteps that by bounding ROUNDS instead of vertices: run exactly k+1 relaxation rounds, where each round lets every flight try to improve a price using ONLY the prices frozen at the start of that round. That freeze is what caps a path at one extra flight per round, so after k+1 rounds every price reflects the cheapest route using at most k+1 flights — exactly the k-stops limit. Animated on: 3 cities, flights 0->1 for 100, 1->2 for 100, 0->2 for 500, src = 0, dst = 2, at most k = 1 stop — find the cheapest price from 0 to 2..