Bottleneck / Minimax Paths

In many grid and graph problems a path isn't judged by the sum of its weights. It's judged by its single worst step (the bottleneck), by its weakest cell, or by the product of its probabilities. Dijkstra handles all of these with one change: how you combine the cost so far with the next edge.

The idea#

To see why one change is enough, look at what Dijkstra relies on. It needs only one property: extending a path can never make it better. Then the first time a node is popped from the heap, no other path waiting in the heap can beat it, so its value is final. Sums of non-negative weights have this property, and so do these:

Path cost	Combine step	Never gets better because...	Heap
Sum of weights	`cost + w`	weights are non-negative	min-heap
Largest step on the path (minimize it)	`max(cost, w)`	a max can only grow	min-heap
Smallest cell on the path (maximize it)	`min(cost, v)`	a min can only shrink	max-heap (negate)
Product of probabilities (maximize it)	`cost * p`	every `p` is at most 1	max-heap (negate)

Two of these rows want the largest value, which raises a practical problem. Python's heapq is a min-heap, so for "maximize" problems you push the negated value and negate it back when you pop.

How to spot it#

The wording describes a path, but the score is not a total.

"Minimize the maximum absolute difference between consecutive cells" (effort).
"Maximize the minimum value on the path" (score, safeness, bandwidth).
"The time you can reach the end is the highest elevation you pass" (rising water).
"Maximize the probability of success along the path."

Template#

This is plain Dijkstra with one line changed: the combine step. For a "maximize" problem, store negated values so the min-heap pops the best path first.

heap = [(start value, source)]
done = empty set
while heap is not empty:
    cost, node = pop the smallest from heap
    if node is the target: return cost   # first pop is final
    if node in done: skip                # stale entry
    add node to done
    for each (next, w) next to node:
        if next not in done:
            push (combine(cost, w), next) onto heap
return the unreachable value             # 0 or -1

To switch problems, change three things: the start value, the combine step and the heap order. Each cell is finalized once and pushed at most once per neighbor, so a grid costs $O(mn \log(mn))$ time and $O(mn)$ space.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Summing when the problem wants the max (or min) along the path.
Forgetting to negate for a "maximize" problem, or negating on push but not on pop.
Writing the "already finalized" check as a value comparison and inverting it; a membership check is simpler.
Marking cells visited when they are pushed instead of when they are popped.
Missing the "unreachable" return at the end (0 or -1, depending on the problem).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Path With Minimum Effort.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Path With Minimum Effort

A path's effort is its largest height difference between neighboring cells. Start at 0, use a min-heap, and combine with max(effort, step), where step is the absolute height difference.

Hint: Path With Maximum Minimum Value

Combine with min, and you want the largest result, so negate. Start with -grid[0][0] and push -min(-score, grid[nr][nc]).

Hint: Swim in Rising Water

The time to reach the end is the highest elevation on the path. Start with grid[0][0] and push max(t, grid[nr][nc]) on a min-heap, for $O(n^2 \log n)$ . A second approach also works: binary search on the answer $t$ and check with a BFS that only steps on cells at most $t$ . That is $O(\log n \cdot n^2)$ as well, since the values go up to $n^2$ . See Binary Search on the Answer.

Hint: Find the Safest Path in a Grid

Two algorithms run in a row. A cell's safeness is its distance to the nearest thief, so first fill a distance grid with a multi-source BFS from every thief. Then run a max-min search on that grid. If the target is never popped, return 0.

Hint: Path with Maximum Probability

Probabilities multiply, and each is at most 1, so a longer path never becomes more likely. Start with -1.0 and push score * p, where score is already negative. Skip a finalized node with a plain if node in done: continue; a value comparison is easy to get backwards once the values are negated.

Key takeaways#

Dijkstra works whenever extending a path can't improve it: sums, maxes, mins and products of values at most 1.
Only the combine step (+, max, min, *) and the heap direction change.
Negate values to get a max-heap from heapq.
Return when the target is popped, and skip stale entries.
Some problems chain two algorithms: BFS to build a cost grid, then Dijkstra over it.

Core idea#

Some paths are judged by their worst step, their weakest cell or a product, not a sum. Dijkstra still works. Change only the combine step and the heap direction.

Key points#

Dijkstra needs one property: extending a path can never make it better.
Then the first pop of a node is final.
Python's heapq is a min-heap. For "maximize" problems, push the negated value and negate it back on pop.
Return when the target is popped. Skip stale entries.
Mark a cell done when you pop it, not when you push it.
A grid costs $O(mn \log(mn))$ time and $O(mn)$ space.
Find the Safest Path chains two algorithms. Multi-source BFS builds a distance grid, then a max-min search runs on it.
Swim in Rising Water also works with binary search on the answer plus a BFS check.

Combine step#

Path cost	Combine	Heap
Sum of weights	`cost + w`	min-heap
Largest step (minimize)	`max(cost, w)`	min-heap
Smallest cell (maximize)	`min(cost, v)`	max-heap (negate)
Product of probabilities	`cost * p`	max-heap (negate)

Template#

heap = [(start value, source)]; done = empty set
while heap is not empty:
    cost, node = pop the smallest from heap
    if node is the target: return cost   # first pop is final
    if node in done: skip                # stale entry
    add node to done
    for each (next, w) next to node, not in done:
        push (combine(cost, w), next)    # max, min, + or *
return the unreachable value             # 0 or -1

Pitfalls#

Summing when the problem wants the max or min along the path.
Negating on push but not on pop.
Writing the "already finalized" check as a value comparison. A membership check is simpler.
Missing the unreachable return (0 or -1).

Say it in an interview#

"A max can only grow along a path, so the greedy pop is still final."
"Only the combine line and the heap order change from plain Dijkstra."