Shortest paths by Dijkstra: beyond plain distances
Dijkstra works for any cost that never decreases along a path: sums, maximums, waiting times. Recognising the cost is the whole problem.
What the pattern is
Dijkstra's algorithm needs one property: extending a path never makes its cost smaller. Ordinary sums of non-negative weights have it, but so do other costs:
- The largest step on the path ("minimum effort": the biggest height difference along the route). The cost of a path is max(cost so far, next step), which never goes down.
- The time you can start ("swim in rising water": you can enter a cell once the water reaches its height). The cost is max(time so far, height of the next cell).
- Sums with state: cost per (node, stops used) for "at most k stops", or per (cell, fuel left).
With such a cost, the unsettled state with the smallest cost is final, exactly as in the ordinary algorithm. Only the combine step changes.
Generalised Dijkstra
best(start)
- Push (cost of start, start) into a min-heap.
- Pop the cheapest state; skip it if already settled; settle it; return its cost if it is the goal.
- For each move to a neighbour: newCost = combine(cost, move). Push it if it improves the neighbour.
How to recognise it
- "Minimum cost", "least time", "minimum effort", "lowest maximum", "earliest time you can reach".
- Moves have different costs, so plain breadth-first search is wrong.
- The cost of extending a path never decreases. If it can (negative weights), use Bellman–Ford.
Minimax problems also have a second solution: binary search on the answer, checking reachability with a search that only uses steps within the limit. Dijkstra is usually shorter to write.
TimeO(E log V)
SpaceO(V)
On a grid, V = rows · cols and E ≈ 4V.
The problems in this module: