The Tropical Semiring

Pillar: Set — "A semiring is two operations on a SET: \(\oplus\) (combine) and \(\otimes\) (extend), where \(\otimes\) distributes over \(\oplus\)."

Pillar: Chain — "Matrix exponentiation over any semiring = Chain compression over that semiring's operations."

---

The Setup

You already know matrix exponentiation from Ch10 L1. You take a transition matrix, raise it to the \(k\)-th power, and read off the answer. That gives you the \(k\)-th term of a linear recurrence in \(O(n^3 \log k)\).

But here's a question that should bother you: why does matrix multiplication use \(+\) and \(\times\)? What if you replaced them with different operations?

Consider this concrete problem. You have a weighted directed graph with \(n\) nodes and you want the shortest path from node \(1\) to node \(n\) using exactly \(k\) edges. Not "at most \(k\)" — exactly \(k\).

Build the adjacency matrix \(M\) where \(M[i][j]\) is the weight of the edge from \(i\) to \(j\) (or \(+\infty\) if no edge exists). Now define a "multiplication" where instead of multiplying entries and adding them up, you ADD entries and take the MINIMUM:

\[(A \otimes B)[i][j] = \min_k \big( A[i][k] + B[k][j] \big)\]

Compute \(M^k\) under this operation. The entry \(M^k[1][n]\) is the shortest path from \(1\) to \(n\) using exactly \(k\) edges.

This isn't a trick. This is a full algebraic framework called the tropical semiring, and it turns shortest-path problems into linear algebra.

---

What Is a Semiring?

In Ch1 L2, you saw that a monoid is a set with one associative operation and an identity. A semiring goes one step further: it's a set with TWO operations.

A semiring is a set \(S\) equipped with two binary operations \(\oplus\) ("addition") and \(\otimes\) ("multiplication") satisfying:

1. \((S, \oplus)\) is a commutative monoid with identity \(\mathbf{0}\) (the "zero").
2. \((S, \otimes)\) is a monoid with identity \(\mathbf{1}\) (the "one").
3. \(\otimes\) distributes over \(\oplus\): \(a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)\).
4. \(\mathbf{0}\) annihilates under \(\otimes\): \(a \otimes \mathbf{0} = \mathbf{0} \otimes a = \mathbf{0}\).

The names "zero" and "one" are suggestive but don't take them literally. In different semirings, the "zero" might be \(+\infty\) and the "one" might be \(0\). What matters is the structural role they play.

Why two operations? Because matrix multiplication NEEDS two operations — one to combine entries within a cell (the "sum" over \(k\)), and one to pair up entries from the two matrices (the "product" of \(A[i][k]\) and \(B[k][j]\)). Distributivity is what guarantees the resulting matrix multiplication is associative, which is what makes exponentiation by squaring work.

---

The Standard Semiring

The one you already know: \((\mathbb{R}, +, \times)\).

Property	Check
\(\oplus = +\) commutative monoid	\(+\) is commutative, associative, identity \(0\)
\(\otimes = \times\) monoid	\(\times\) is associative, identity \(1\)
Distributivity	\(a \times (b + c) = ab + ac\)
Zero annihilation	\(a \times 0 = 0\)

Standard matrix multiplication uses this semiring:

\[(AB)[i][j] = \sum_k A[i][k] \cdot B[k][j]\]

What does \(M^k[i][j]\) compute in the standard semiring? It counts the number of weighted paths of exactly \(k\) edges from \(i\) to \(j\), where each path's contribution is the product of its edge weights. For an unweighted graph (all weights \(= 1\)), \(M^k[i][j]\) is simply the number of distinct paths of length \(k\) from \(i\) to \(j\).

Trace it for a tiny graph. Three nodes, edges \(1 \to 2\), \(2 \to 3\), \(1 \to 3\):

\[M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}\]

\[M^2[1][3] = M[1][1] \cdot M[1][3] + M[1][2] \cdot M[2][3] + M[1][3] \cdot M[3][3] = 0 + 1 \cdot 1 + 0 = 1\]

One path of length \(2\) from node \(1\) to node \(3\): \(1 \to 2 \to 3\). The matrix got it right.

---

The Tropical Semiring

Now swap the operations. The tropical semiring (also called the min-plus semiring) is:

\[(\mathbb{R} \cup \{+\infty\},\; \min,\; +)\]

Role	Operation	Identity
\(\oplus\) ("addition")	\(\min\)	\(+\infty\) (the "zero")
\(\otimes\) ("multiplication")	\(+\)	\(0\) (the "one")

Wait — \(+\infty\) is the "zero"? And \(0\) is the "one"? Yes. \(\min(a, +\infty) = a\) for all \(a\), so \(+\infty\) is the identity for \(\min\). And \(a + 0 = a\), so \(0\) is the identity for \(+\). The names refer to structural roles, not numerical values.

And "zero annihilation" means \(a + (+\infty) = +\infty\) — adding anything to infinity gives infinity. This is \(a \otimes \mathbf{0} = \mathbf{0}\) in semiring language.

Proving Distributivity

This is the property that makes the whole framework work. You need to verify:

\[a + \min(b, c) = \min(a + b, a + c)\]

This is the claim that \(+\) distributes over \(\min\). Here's the proof.

Case 1: \(b \leq c\). Then \(\min(b, c) = b\), so the left side is \(a + b\). On the right side, \(a + b \leq a + c\) (adding the same \(a\) to both sides preserves the inequality), so \(\min(a + b, a + c) = a + b\). Both sides equal \(a + b\). \(\checkmark\)

Case 2: \(b > c\). Symmetric. \(\min(b, c) = c\), left side is \(a + c\). Right side: \(a + c < a + b\), so \(\min(a + b, a + c) = a + c\). \(\checkmark\)

The key fact used: addition preserves order. If \(b \leq c\), then \(a + b \leq a + c\). This is why the tropical semiring works over \(\mathbb{R}\) (and even over \(\mathbb{Z}\)) but would NOT work if you replaced \(+\) with an operation that doesn't preserve order.

---

Tropical Matrix Multiplication

Replace \(\sum\) with \(\min\) and \(\cdot\) with \(+\) in the standard matrix product:

\[(A \otimes B)[i][j] = \min_k \big( A[i][k] + B[k][j] \big)\]

Read this out loud: "To get from \(i\) to \(j\), try every intermediate node \(k\). The cost through \(k\) is the cost from \(i\) to \(k\) plus the cost from \(k\) to \(j\). Take the minimum."

That's exactly the relaxation step in shortest-path algorithms.

Worked Example

Three nodes. Edge weights:

\[M = \begin{pmatrix} +\infty & 3 & 8 \\ +\infty & +\infty & 2 \\ +\infty & +\infty & +\infty \end{pmatrix}\]

Edge \(1 \to 2\) has weight \(3\), edge \(1 \to 3\) has weight \(8\), edge \(2 \to 3\) has weight \(2\). No other edges.

Compute \(M^2\) (shortest paths using exactly \(2\) edges):

\[M^2[1][3] = \min\big( M[1][1] + M[1][3],\; M[1][2] + M[2][3],\; M[1][3] + M[3][3] \big)\]

\[= \min\big( +\infty + 8,\; 3 + 2,\; 8 + \infty \big) = \min(+\infty, 5, +\infty) = 5\]

The shortest path from \(1\) to \(3\) using exactly \(2\) edges is \(1 \to 2 \to 3\) with cost \(3 + 2 = 5\).

All other entries of \(M^2\):

Entry	Computation	Value
\(M^2[1][1]\)	\(\min(+\infty, +\infty, +\infty)\)	\(+\infty\)
\(M^2[1][2]\)	\(\min(+\infty, +\infty, +\infty)\)	\(+\infty\)
\(M^2[1][3]\)	\(\min(+\infty, 5, +\infty)\)	\(5\)
\(M^2[2][2]\)	\(\min(+\infty, +\infty, +\infty)\)	\(+\infty\)
\(M^2[2][3]\)	\(\min(+\infty, +\infty, +\infty)\)	\(+\infty\)
\(M^2[3][3]\)	\(\min(+\infty, +\infty, +\infty)\)	\(+\infty\)

Only \(M^2[1][3]\) is finite — the only \(2\)-edge path in this graph is \(1 \to 2 \to 3\).

---

Floyd-Warshall Is Tropical Matrix Power

Here's the punchline. Floyd-Warshall computes all-pairs shortest paths. It runs three nested loops and relaxes distances through intermediate nodes. That's the same structure as matrix multiplication — the middle loop iterates over the "intermediate" dimension \(k\).

More precisely:

• \(M^1 = M\): shortest paths using exactly \(1\) edge.
• \(M^2\): shortest paths using exactly \(2\) edges.
• \(M^k\): shortest paths using exactly \(k\) edges.

If you want shortest paths using AT MOST \(k\) edges, you compute \(I \oplus M \oplus M^2 \oplus \cdots \oplus M^k\), where \(I\) is the tropical identity matrix (\(0\) on the diagonal, \(+\infty\) elsewhere) and \(\oplus\) is element-wise \(\min\).

For a graph with \(n\) nodes and no negative-weight cycles, any shortest path uses at most \(n - 1\) edges. So the all-pairs shortest path matrix is:

\[D = I \oplus M \oplus M^2 \oplus \cdots \oplus M^{n-1}\]

Floyd-Warshall computes this in \(O(n^3)\) by cleverly ordering the relaxations. Tropical matrix exponentiation computes \(M^k\) in \(O(n^3 \log k)\), which is worse for "all-pairs shortest paths" but better when you need shortest paths of EXACTLY \(k\) edges — Floyd-Warshall can't do that at all.

This is the power of the semiring abstraction. You don't need to reinvent a new algorithm for each problem. You pick the semiring, plug it into matrix exponentiation, and the algebra does the rest.

---

The Semiring Table

The tropical semiring is one member of a family. Each semiring answers a different question about paths in a graph.

Semiring	\(\oplus\)	\(\otimes\)	\(\mathbf{0}\)	\(\mathbf{1}\)	\(M^k[i][j]\) computes
Standard \((\mathbb{Z}, +, \times)\)	\(+\)	\(\times\)	\(0\)	\(1\)	Sum of products of edge weights over all \(k\)-edge paths
Counting \((\mathbb{Z}_{\geq 0}, +, \times)\)	\(+\)	\(\times\)	\(0\)	\(1\)	Number of \(k\)-edge paths (unweighted)
Boolean \((\{\text{false}, \text{true}\}, \vee, \wedge)\)	OR	AND	false	true	Does a \(k\)-edge path exist? (Reachability)
Tropical \((\mathbb{R} \cup \{+\infty\}, \min, +)\)	\(\min\)	\(+\)	\(+\infty\)	\(0\)	Shortest \(k\)-edge path
Arctic \((\mathbb{R} \cup \{-\infty\}, \max, +)\)	\(\max\)	\(+\)	\(-\infty\)	\(0\)	Longest \(k\)-edge path
Bottleneck \((\mathbb{R} \cup \{-\infty\}, \max, \min)\)	\(\max\)	\(\min\)	\(-\infty\)	\(+\infty\)	Maximum bottleneck over \(k\)-edge paths

Each row is a semiring. Each satisfies the four axioms. Each plugs into the same matrix exponentiation code — you just swap out the two operations and their identities.

The Boolean semiring deserves a note: \(M^k[i][j] = \text{true}\) iff there exists a path of exactly \(k\) edges from \(i\) to \(j\). Transitive closure is \(I \vee M \vee M^2 \vee \cdots \vee M^{n-1}\), computed with Boolean matrix multiplication. This is Warshall's algorithm — a special case of Floyd-Warshall over the Boolean semiring.

The Arctic semiring (\(\max, +\)) is sometimes called the "max-plus" semiring. It finds longest paths. Verify the distributivity yourself: \(a + \max(b, c) = \max(a + b, a + c)\). The same proof as tropical, with the inequality flipped.

---

The Tropical Identity Matrix

The identity matrix under tropical multiplication has \(0\) on the diagonal and \(+\infty\) elsewhere:

\[I = \begin{pmatrix} 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \\ +\infty & +\infty & 0 \end{pmatrix}\]

Check: \((I \otimes M)[i][j] = \min_k(I[i][k] + M[k][j])\). When \(k = i\), the term is \(0 + M[i][j] = M[i][j]\). For \(k \neq i\), the term is \(+\infty + M[k][j] = +\infty\). So the minimum is \(M[i][j]\), and \(I \otimes M = M\). The "one" (\(= 0\)) on the diagonal means "zero cost to stay in place." The "zero" (\(= +\infty\)) off the diagonal means "no direct edge."

This is what goes into the initial result matrix in the exponentiation-by-squaring code.

---

The Code

Tropical Matrix Multiply

typedef vector<vector<long long>> Matrix;
const long long TROPICAL_ZERO = 2e18;

Matrix tropicalMultiply(Matrix& left, Matrix& right) {
    int dimension = left.size();
    Matrix product(dimension, vector<long long>(dimension, TROPICAL_ZERO));
    for (int row = 0; row < dimension; row++) {
        for (int col = 0; col < dimension; col++) {
            for (int mid = 0; mid < dimension; mid++) {
                if (left[row][mid] < TROPICAL_ZERO && right[mid][col] < TROPICAL_ZERO) {
                    product[row][col] = min(product[row][col], left[row][mid] + right[mid][col]);
                }
            }
        }
    }
    return product;
}

The if guard prevents adding two large values and overflowing. If either entry is \(+\infty\), the sum is \(+\infty\) — no point computing it. The initial fill of TROPICAL_ZERO (\(= 2 \times 10^{18}\)) serves as \(+\infty\).

Tropical Matrix Power

Matrix tropicalMatpow(Matrix base, long long exponent) {
    int dimension = base.size();
    Matrix result(dimension, vector<long long>(dimension, TROPICAL_ZERO));
    for (int i = 0; i < dimension; i++) result[i][i] = 0;
    while (exponent > 0) {
        if (exponent & 1) result = tropicalMultiply(result, base);
        base = tropicalMultiply(base, base);
        exponent >>= 1;
    }
    return result;
}

Identical structure to standard matrix exponentiation from Ch10 L1. The identity matrix has \(0\) on the diagonal (the tropical "one") and TROPICAL_ZERO elsewhere (the tropical "zero"). The only change from Ch10 L1 is which multiply function you call.

That's the whole point: the semiring abstraction means you write the exponentiation logic ONCE and swap in whatever operations you need.

---

Complexity

\(O(n^3 \log k)\) time, \(O(n^2)\) space — where \(n\) is the matrix dimension (number of nodes) and \(k\) is the exponent (path length).

---

Common Mistakes

• Overflow when adding two large values. If both \(A[i][k]\) and \(B[k][j]\) are close to LLONG_MAX, their sum overflows. Use a sentinel like \(2 \times 10^{18}\) as infinity and guard additions with an if check. Never use LLONG_MAX as infinity in tropical arithmetic.
• Wrong identity matrix. The tropical identity has \(0\) on the diagonal and \(+\infty\) off it — not \(+\infty\) everywhere and not the standard identity. If you initialize result to all zeros, you're saying "every node is distance \(0\) from every other node," which gives garbage answers.
• Confusing "exactly \(k\) edges" with "at most \(k\) edges." \(M^k\) gives paths of exactly \(k\) edges. If the problem asks for "at most \(k\)," you need \(I \oplus M \oplus M^2 \oplus \cdots \oplus M^k\). A common trick: add a self-loop of weight \(0\) to every node (set \(M[i][i] = 0\)). Then "exactly \(k\) edges" includes paths that "waste" edges by looping in place, which effectively gives "at most \(k\)."

---

Quick Recap

• A semiring \((S, \oplus, \otimes)\) has two operations: \(\oplus\) is a commutative monoid, \(\otimes\) is a monoid, \(\otimes\) distributes over \(\oplus\), and \(\mathbf{0}\) annihilates.
• The tropical semiring is \((\mathbb{R} \cup \{+\infty\}, \min, +)\) with \(\mathbf{0} = +\infty\) and \(\mathbf{1} = 0\). Distributivity holds because addition preserves order.
• Tropical matrix multiplication \((A \otimes B)[i][j] = \min_k(A[i][k] + B[k][j])\) computes shortest paths.
• \(M^k\) under tropical multiplication gives shortest paths using exactly \(k\) edges. Floyd-Warshall is the tropical closure \(I \oplus M \oplus \cdots \oplus M^{n-1}\).
• Swap in a different semiring (Boolean, Arctic, Bottleneck) to answer different path questions with the same matrix exponentiation code.

---

Problems

Problem	Link	Difficulty	Focus
CSES — Graph Paths II	cses.fi/problemset/task/1724	Medium	Tropical matrix exponentiation for shortest \(k\)-edge paths
CSES — Graph Paths I	cses.fi/problemset/task/1723	Medium	Standard semiring: counting \(k\)-edge paths
CSES — Shortest Routes I	cses.fi/problemset/task/1671	Easy	Dijkstra as a warm-up; compare with tropical approach
LC 1334 — Find the City With the Smallest Number of Neighbors	leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance	Medium	Floyd-Warshall (tropical closure)