Min-Plus Matrix Monoid
(monoid/min_plus_matrix.hpp)
- View this file on GitHub
- Last update: 2026-07-21 20:17:47+09:00
- Include:
#include "monoid/min_plus_matrix.hpp"
Overview
A monoid for range matrix multiplication over the Min-Plus (Tropical) semiring.
In this algebra, the standard addition operation is replaced by std::min, and the standard multiplication operation is replaced by regular addition +.
This is highly effective for solving Dynamic DP problems (where state transitions involve taking the minimum of sums) or finding shortest paths over dynamic edge weights on a Segment Tree.
Merging two matrices takes $O(N^3)$ time, so $N$ should be kept small.
Example
#include "ds/segtree/segtree.hpp"
#include "monoid/min_plus_matrix.hpp"
#include <iostream>
#include <vector>
// 2x2 Min-Plus Matrix with long long
using MinMat = m1une::monoid::MinPlusMatrix<long long, 2>;
int main() {
int N = 3;
std::vector<MinMat::value_type> init_data(N);
// Initialize state transitions
for (int i = 0; i < N; ++i) {
auto mat = MinMat::make_inf();
mat[0][0] = 5; // Transition cost from state 0 to 0
mat[0][1] = 2; // Transition cost from state 1 to 0
mat[1][0] = 3; // Transition cost from state 0 to 1
mat[1][1] = 0; // Transition cost from state 1 to 1
init_data[i] = mat;
}
m1une::ds::Segtree<MinMat> seg(init_data);
// Get the transition matrix for the range [0, 3)
auto res = seg.prod(0, N);
// Output the shortest path cost from initial state j to final state i
std::cout << "Cost 0 -> 0: " << res[0][0] << "\n";
std::cout << "Cost 1 -> 0: " << res[0][1] << "\n";
return 0;
}
Interface and Complexity
This is a stateless algebra tag. Generic data structures use its public
value_type, id(), and op(a, b) members. If the type also provides helpers
such as make(...) or inv(x), they are described above or in the documented
properties.
Each static operation runs in the cost of the underlying operation shown in the
properties. Scalar monoids are $O(1)$; monoids whose value_type stores several
items, permutations, or matrices scale with that stored size.
Verified with
Code
#ifndef M1UNE_MONOID_MIN_PLUS_MATRIX_HPP
#define M1UNE_MONOID_MIN_PLUS_MATRIX_HPP 1
#include <algorithm>
#include <array>
#include <limits>
namespace m1une {
namespace monoid {
// Monoid for fixed-size square matrix multiplication over the Min-Plus (Tropical) semiring.
// Useful for Dynamic DP (Minimization) and Shortest Path problems.
template <typename T, int N, T Inf = std::numeric_limits<T>::max() / 2>
struct MinPlusMatrix {
using value_type = std::array<std::array<T, N>, N>;
static constexpr bool commutative = false;
// The identity matrix for min-plus algebra.
// Diagonal elements are 0 (identity for addition).
// Off-diagonal elements are Inf (identity for min).
static constexpr value_type id() {
value_type res{};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res[i][j] = (i == j) ? T(0) : Inf;
}
}
return res;
}
// Multiplies two min-plus matrices: c_{i, j} = min_k (a_{i, k} + b_{k, j})
static constexpr value_type op(const value_type& a, const value_type& b) {
value_type res{};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res[i][j] = Inf;
}
}
for (int i = 0; i < N; ++i) {
for (int k = 0; k < N; ++k) {
if (a[i][k] == Inf) continue;
for (int j = 0; j < N; ++j) {
if (b[k][j] == Inf) continue;
res[i][j] = std::min(res[i][j], a[i][k] + b[k][j]);
}
}
}
return res;
}
// Helper to securely create a matrix initialized with Inf.
static constexpr value_type make_inf() {
value_type res{};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res[i][j] = Inf;
}
}
return res;
}
};
} // namespace monoid
} // namespace m1une
#endif // M1UNE_MONOID_MIN_PLUS_MATRIX_HPP#line 1 "monoid/min_plus_matrix.hpp"
#include <algorithm>
#include <array>
#include <limits>
namespace m1une {
namespace monoid {
// Monoid for fixed-size square matrix multiplication over the Min-Plus (Tropical) semiring.
// Useful for Dynamic DP (Minimization) and Shortest Path problems.
template <typename T, int N, T Inf = std::numeric_limits<T>::max() / 2>
struct MinPlusMatrix {
using value_type = std::array<std::array<T, N>, N>;
static constexpr bool commutative = false;
// The identity matrix for min-plus algebra.
// Diagonal elements are 0 (identity for addition).
// Off-diagonal elements are Inf (identity for min).
static constexpr value_type id() {
value_type res{};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res[i][j] = (i == j) ? T(0) : Inf;
}
}
return res;
}
// Multiplies two min-plus matrices: c_{i, j} = min_k (a_{i, k} + b_{k, j})
static constexpr value_type op(const value_type& a, const value_type& b) {
value_type res{};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res[i][j] = Inf;
}
}
for (int i = 0; i < N; ++i) {
for (int k = 0; k < N; ++k) {
if (a[i][k] == Inf) continue;
for (int j = 0; j < N; ++j) {
if (b[k][j] == Inf) continue;
res[i][j] = std::min(res[i][j], a[i][k] + b[k][j]);
}
}
}
return res;
}
// Helper to securely create a matrix initialized with Inf.
static constexpr value_type make_inf() {
value_type res{};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res[i][j] = Inf;
}
}
return res;
}
};
} // namespace monoid
} // namespace m1une