Shortest Paths With Rebate Roads
Problem
A region has n towns numbered 0 to n - 1 and one-way roads given as [u, v, cost]. Some roads pay a rebate, so their cost is negative, but no loop of roads has a negative total. Return the cheapest cost from town src to every town, using None for towns that cannot be reached.
Examples
Input: n = 4, roads = [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], src = 0
Output: [0, 2, 5, 4]
Why: going 0 to 2 to 1 costs 5 - 3 = 2, cheaper than the direct road to 1 that costs 4Input: n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Why: town 2 has no road leading into itInput: n = 1, roads = [], src = 0
Output: [0]
Why: edge case, the start town costs nothing to reachHints
0 / 3
In the first example, town 1 looks settled at cost 4 before the rebate road through town 2 is seen. Why does that break the usual cheapest-first approach?
Relaxing a road means lowering the cost of its end town if going through its start town is cheaper. A cheapest path has at most n - 1 roads, and each full pass over the roads fixes at least one more road of every cheapest path.
Set every cost to infinity except src. Repeat n - 1 times: for every road, relax it. Stop early if a whole pass changes nothing. Turn the costs still at infinity into None.
Solution
Bellman-Ford does not trust any cost until enough passes have run. After pass k, every town whose cheapest path uses at most k roads has its final cost, because that path's last road was relaxed after its second-to-last town was already correct. A cheapest path never repeats a town when no loop has a negative total, so n - 1 passes are enough, and a pass with no change means every cost is final already. Cheapest-first search fails here because a rebate road found later can undercut a town it already settled. Time is O(n · m) for m roads, and space is O(n).
def cheapest_from(n, roads, src):
INF = float("inf")
cost = [INF] * n
cost[src] = 0
for _ in range(n - 1): # a cheapest path uses at most n - 1 roads
changed = False
for u, v, c in roads:
if cost[u] != INF and cost[u] + c < cost[v]:
cost[v] = cost[u] + c # relax the road
changed = True
if not changed: # nothing moved: every cost is final
break
return [x if x != INF else None for x in cost]
print(cheapest_from(4, [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], 0)) # -> [0, 2, 5, 4]
print(cheapest_from(3, [[0, 1, -2]], 0)) # -> [0, -2, None]
print(cheapest_from(1, [], 0)) # -> [0]Stuck on the idea rather than the code? Bellman-Ford covers it.