Dijkstra's algorithm, generalized per Knuth (Knuth 1977), is a schema for solving the algebraic path problem by greedy frontier expansion, parameterized by a routing algebra (an ordered semiring). Fix the algebra to (min, +) and you get shortest paths. Fix it to (min, max) and the same finalize-on-pop schema computes the lowest-ridge-to-the-boundary level for every interior cell of a height field, which is 2D Trapping Rain Water (LeetCode 407). Fix it to (max, min) and you get widest paths.

The priority-queue-from-boundary algorithm for LC 407, and its characterization as a bottleneck shortest-path problem, are both standard – documented across public LC 407 write-ups. This document's contribution is the explicit (min, max) semiring and the algebra-as-data framing shared across all three instances.

The correctness of the greedy finalize-on-pop invariant has nothing to do with +. It depends on two structural facts about the algebra:

• ⊕ is selective — combine returns one of its arguments, so a popped node carries a single finalized value and induces a total/partial order a ⪯ b ⇔ a ⊕ b = a.
• ⊗ is monotone (inflationary) — extending a path cannot make it more preferred: a ⪯ a ⊗ c for all c.

Under those, the first time a node is popped its value is final. Everything else is the same loop.

⊗ differs across all three rows; ⊕ and the seed set differ too, per the table above – only the solver loop itself stays fixed. The rainwater scalar is a post-pass: trapped = Σ max(0, level(v) − h[v]).

Sobrinho (Sobrinho 2002, 2005) isolates the two independent properties:

• Monotonicity (inflationary): a ⪯ a ⊗ c. Buys termination and finalize-on-pop. The exact analogue of "non-negative weights."
• Isotonicity: a ⪯ b ⇒ (c ⊗ a) ⪯ (c ⊗ b). Buys global optimality — optimal substructure holds.

For (min, max): both hold unconditionally, because max(a, c) ≥ a always. This is why 2D rainwater needs no Bellman-Ford fallback.

LeetCode 42 (1D) has no Dijkstra content. The graph is a line, so bottleneck-to-escape collapses to min(prefixMax, suffixMax) − h[i]. No frontier, no priority queue. The 2D problem is the first case where competing ridges require a selection — which is the work ⊕ does.

(require '[wal-sh.tools.dijkstra-explorer.core :as d])

;; LC407 -- the canonical test
(let [g d/lc407
      final (d/solve g (d/algebra-by-id :bottleneck))]
  (d/trapped g final))

The algebra IS data – a map of pure functions:

{:id       :bottleneck
 :sel      :min
 :seeds    boundary
 :seed-key (fn [g c] (nth (:h g) c))
 :extend   (fn [g acc v] (max acc (nth (:h g) v)))}

The solver is (take-while some? (iterate step (init g A))). Adding a fourth semiring is a def, not a type.

The claim "2D rainwater is Dijkstra over (min, max)" breaks when:

• ⊗ ceases to be monotone – siphoning, evaporation, mid-path drains. Fallback: Bellman-Ford.
• ⊗ ceases to be isotone – composite QoS metrics. Dijkstra terminates but returns non-optimal paths. The silent failure mode.
• ⊕ ceases to be selective – counting semiring (+, ×). No single finalized value per node. Fallback: Gauss-Jordan / Floyd-Warshall.
• The graph degenerates to a line – 1D rainwater. No frontier needed.

Six PBT properties verified across 300 random grids: