When greedy is not allowed

Relax every edge, in rounds. Slower, and it survives the constraint that breaks the greedy version.

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.

1INF = float("inf")2edges = [(0, 1, 100), (1, 2, 100)]3 4best = [0, INF, INF]5snapshot = best[:]                          # the previous round, frozen6for a, b, weight in edges:7    if snapshot[a] != INF and snapshot[a] + weight < best[b]:8        best[b] = snapshot[a] + weight9print("one round, with a snapshot:  ", best)10 11best = [0, INF, INF]12for a, b, weight in edges:13    if best[a] != INF and best[a] + weight < best[b]:14        best[b] = best[a] + weight15print("one round, reading live:     ", best)

Reading live let a single round travel two edges, which is the bug the snapshot prevents.

Quick check· 5 min

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?

An improvement made earlier in the round can be used again later in the same round, so a result may use more edges than the round count allowsThe algorithm would never terminate, because improvements would cascade indefinitelyNegative weights would no longer be handled correctlyNothing; the snapshot is purely an optimization

Problem· 32 min

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.

1INF = float("inf")2edges = [(0, 1, 100), (1, 2, 100)]3 4best = [0, INF, INF]5snapshot = best[:] # the previous round, frozen6for a, b, weight in edges:7 if snapshot[a] != INF and snapshot[a] + weight < best[b]:8 best[b] = snapshot[a] + weight9print("one round, with a snapshot: ", best)10 11best = [0, INF, INF]12for a, b, weight in edges:13 if best[a] != INF and best[a] + weight < best[b]:14 best[b] = best[a] + weight15print("one round, reading live: ", best)