The rider who took the long way round
You have done this today
You order biryani at 8 pm. A rider is assigned, and the app shows an arrival time that is usually right.
What happens behind the screen
The city is a graph. Junctions are nodes, roads are edges, and every road has a cost in minutes, not kilometres. A short road in heavy traffic costs more than a long empty one.
The app cannot try every route. It keeps a table of the best known cost to each junction, and always finishes the cheapest unfinished junction next. Step through it below. Watch what happens to junction A.
Start at the restaurant. Its cost is 0. Everything else is still unknown.
The idea in plain words
This is Dijkstra's algorithm. Start at cost 0, always take the cheapest unfinished node, and check whether going through it makes any neighbour cheaper. Once a node is finished, its cost is final, because any other route to it would have to pass through something at least as expensive.
That promise only holds when no road has a negative cost. A heap makes 'cheapest next' fast, so the work grows like E log V instead of V squared.
Dijkstra with a heap
import heapq
def shortest_times(graph, start):
# graph: {node: [(neighbour, minutes), ...]}
best = {node: float("inf") for node in graph}
best[start] = 0
heap = [(0, start)] # (cost so far, node)
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]: # stale entry, a cheaper way was already found
continue
for nxt, minutes in graph[node]:
new_cost = cost + minutes
if new_cost < best[nxt]:
best[nxt] = new_cost
heapq.heappush(heap, (new_cost, nxt))
return bestIf an interviewer asks
"Find the shortest path in a weighted graph. Why does Dijkstra fail with negative edges?"
You could say
I would use Dijkstra with a min-heap. It finalises the cheapest unfinished node each time, which is only safe if no later path can be cheaper. Negative edges break that guarantee, so for those I would use Bellman-Ford. The complexity is O((V + E) log V).
Check yourself
At step 3 the cost of A dropped from 7 to 5. Why?
Which input breaks Dijkstra's algorithm?
Was this clear?
Up next
Two people, one last seat
How queues and locks decide who gets the final ticket.