Advanced Graphs
When greedy is not allowed
Relax every edge, in rounds. Slower, and it survives the constraint that breaks the greedy version.
Key idea
Two things break the greedy argument
The greedy algorithm finalizes a node the moment it is popped, on the grounds that nothing can improve it later. Two situations break that.
Negative edge weights, where a longer route can become cheaper after taking a negative edge. And a limit on the number of edges used, where a cheaper route with too many edges is not allowed and an expensive short route must be kept.
Both mean a node's best usable answer can change after it would have been finalized, so finalization has to go.
Why it works
Relaxation, and what a round buys
Relaxing an edge means: if the cost to reach its start, plus the edge, beats the current best for its end, record the improvement.
Do that for every edge, then do it again. After one full round, every shortest path using at most one edge is correct. After two rounds, at most two edges. After k rounds, at most k edges.
That is the invariant, and it is also the answer to the edge-limited version: run exactly as many rounds as edges are allowed and stop.
One round is shown below, twice, on a graph where node 2 sits two edges away from the start. The only difference between the two is where the costs are read from.
Gotcha
The snapshot is the whole difficulty
Each round must read the costs as they were at the end of the previous round. Reading the live array lets an improvement made earlier in this round be used again later in the same round, which quietly allows more edges than the round count permits.
That is exactly what the second run above does. Node 2 ends up at 200 after one round, which is a two-edge route bought with a one-edge budget. Copying the array once per round costs almost nothing and is what makes the count mean anything.
For the plain negative-weight version, where there is no edge limit, the snapshot is unnecessary and using the live array only makes it converge sooner. Know which version you are writing.
Tip
What the budget actually changes
Add a direct edge from 0 to 2 costing 500 and the two answers separate. With one edge allowed, node 2 can only be reached by that direct 500, because the cheaper route through node 1 needs two edges. With two allowed, the route through node 1 costs 200 and wins.
So the algorithm is not choosing the cheapest path. It is choosing the cheapest path within the budget, which is a different problem and the reason the greedy version cannot express it.
Key idea
Detecting a negative cycle
For the unlimited version, running one round per node minus one is enough, because no shortest path uses more edges than that. If one more round still improves something, that improvement can be repeated forever, which means a negative cycle exists.
That extra round is the standard cycle test and it costs one more pass. It is worth knowing even when a problem does not ask, because it is the usual follow-up question.
Cost
Cost, and when to accept it
Each round examines every edge, so k rounds cost O(k times E). The full version with no limit is O(V times E), which is much worse than the heap version's O(E log V).
Use it when the greedy precondition fails: negative weights, or a cap on the number of edges. Otherwise the heap version is strictly better. Saying which precondition forced the choice is what an interviewer is listening for.
Why does the snapshot matter?
In the edge-limited version, what goes wrong if each round reads and writes the same array instead of a snapshot of the previous round?
Cheapest Flights Within K Stops
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.