Pattern visualizer
Path with Minimum Effort
The trap in this problem is reaching for a sum, because effort is defined as the worst single step, not the total climb. That single change is what lets Dijkstra apply: relaxing an edge takes the MAX of the path's cost so far and the new edge's weight instead of adding them, and that relaxation still only ever raises or holds a cell's effort — never lowers it once the queue has settled it, which is exactly the property Dijkstra needs to guarantee that popping the smallest remaining effort is final. The picture below turns the grid into a graph: one vertex per cell, one weighted edge per adjacent pair, and a badge on each visited cell showing its settled effort. Animated on: A 3x3 grid of elevations [[1,2,2],[3,8,2],[5,3,5]] — find a path from the top-left to the bottom-right that minimizes the LARGEST absolute height difference between any two consecutive cells on the path, not the total climbed..
Grid as a graph: Dijkstra with a minimax relax instead of a sum
Grid as a graph: one vertex per cell, edge weight = height difference
Every cell becomes a vertex and every edge to a 4-directional neighbor carries the absolute height difference as its weight. A path's cost here is the LARGEST edge it uses, not the sum of edges, so the question is which route keeps that single worst step as small as possible.
1FUNCTION minEffort(heights):2 effort[0][0] <- 0, all others <- INFINITY3 queue <- {(0, 0)}4 WHILE queue NOT EMPTY5 (r, c) <- CELL IN queue WITH MIN effort6 REMOVE (r, c) FROM queue7 IF (r, c) = (m - 1, n - 1)8 RETURN effort[r][c]9 FOR EACH neighbor (nr, nc) OF (r, c)10 cost <- MAX(effort[r][c], ABS(heights[r][c] - heights[nr][nc]))11 IF cost < effort[nr][nc]12 effort[nr][nc] <- cost13 ADD (nr, nc) TO queue
← / → step · space play · Home restart