Cheapest Route Between Two Stops
Problem
A delivery map has n stops numbered 0 to n - 1 and one-way roads given as [u, v, cost], where every cost is zero or more. Return the cheapest total cost of driving from stop src to stop dst, or -1 if dst cannot be reached.
Examples
Input: n = 5, roads = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], src = 0, dst = 4
Output: 7
Why: 0 to 2 to 1 to 3 to 4 costs 1 + 2 + 1 + 3, cheaper than the direct road to 1 that costs 4 on its ownInput: n = 3, roads = [[0, 1, 2]], src = 0, dst = 2
Output: -1
Why: no road leads into stop 2Input: n = 2, roads = [[0, 1, 5]], src = 1, dst = 1
Output: 0
Why: edge case, the route is already at its destinationHints
0 / 3
Breadth-first search finds the fewest roads, not the cheapest total. With costs on the roads, which stop can you be sure about first?
The unsettled stop with the smallest known cost can never get cheaper, because every other route to it would pass through a stop that already costs at least as much. Settle that one and update its neighbours.
Keep a min-heap of (cost so far, stop), starting with (0, src). Pop the cheapest entry, skip it if a cheaper cost for that stop is already known, and return its cost when the stop is dst. Otherwise push every neighbour whose cost improves.
Solution
Dijkstra's algorithm settles stops in order of their cheapest cost. Because no road has a negative cost, the stop at the top of the min-heap cannot be reached more cheaply later, so the first time dst is popped its cost is final and the search can stop. A stop may be pushed several times as cheaper routes are found, and the older, more expensive entries are skipped when they surface. With m roads, time is O((n + m) log n) and space is O(n + m).
import heapq
def cheapest_route(n, roads, src, dst):
graph = [[] for _ in range(n)]
for u, v, cost in roads:
graph[u].append((v, cost))
best = [float("inf")] * n
best[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if u == dst:
return d # the first pop of dst is final
if d > best[u]:
continue # an older, more expensive entry
for v, cost in graph[u]:
if d + cost < best[v]:
best[v] = d + cost
heapq.heappush(heap, (best[v], v))
return -1
print(cheapest_route(5, [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], 0, 4)) # -> 7
print(cheapest_route(3, [[0, 1, 2]], 0, 2)) # -> -1
print(cheapest_route(2, [[0, 1, 5]], 1, 1)) # -> 0Stuck on the idea rather than the code? Dijkstra's Algorithm covers it.