The Algebraic Path Problem
Dijkstra is one solver, the semiring is the knob

Dijkstra's algorithm is not "an algorithm for shortest paths." It 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 identical machine computes the lowest-ridge-to-the-boundary level for every interior cell of a height field — which is exactly 2D Trapping Rain Water (LeetCode 407). Fix it to (max, min) and you get widest paths.

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.

The only line of code that differs is ⊗. The rainwater scalar is a post-pass: trapped = Σ max(0, level(v) − h[v]).

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:

• Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.
• Knuth, D. E. (1977). A generalization of Dijkstra's algorithm. Information Processing Letters 6(1), 1-5.
• Sobrinho, J. L. (2002). Algebra and algorithms for QoS path computation. IEEE/ACM ToN 10(4), 541-550.
• Sobrinho, J. L. (2005). An algebraic theory of dynamic network routing. IEEE/ACM ToN 13(5), 1160-1173.
• Dolan, S. (2013). Fun with Semirings. ICFP 2013.
• Gondran, M., & Minoux, M. (2008). Graphs, Dioids and Semirings. Springer.
• Kildall, G. (1973). A unified approach to global program optimization. POPL 1973.
• Goodman, J. (1999). Semiring parsing. Computational Linguistics 25(4), 573-605.
• Baras, J. S., & Theodorakopoulos, G. (2010). Path Problems in Networks. Morgan & Claypool.