Min-plus matrix multiplication implementation

Question

I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication:

One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph.

I had a look at min-plus matrix multiplication, but can't quite understand what $min$ is doing in the description of the algorithm:

Given two $n \times n$ matrices $A = (a_{ij})$ and $B = (b_{ij})$, their distance product $C = (c_{ij}) = A \star B$ is defined as an $n \times n$ matrix such that $c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}$. This is standard matrix multiplication for the semi-ring of tropical numbers in the min convention.

What is the $min$ function here? When I think of $min$, I think of it like $min(1, 2) = 1$. But how does that make sense if we are doing a sum?

So, in my implementation of regular matrix multiplication, finding the value for $c_{ij}$ looks like this:

    for j := 0; j < p; j++ {
        sum := 0

        for k := 0; k < m; k++ {
            sum += A[i][k] * B[k][j]
        }

        C[i][j] = sum
    }

But if I add a $min$ (or a $max$) function here, like so:

...
sum += min(A[i][k] * B[k][j])
...

That doesn't make sense at all.

So how would one describe an implementation of the $min$ function described in the article for min-plus matrix multiplication? It is the $min$ of what?

Answer 1

In the tropical semiring, the "addition" operation is the minimum, and the "multiplication" operation is addition.

If you want to adapt matrix multiplication to the tropical semiring, you literally need to replace every occurrence of $+$ with $\min$, and $*$ with $+$.

To this effect, look at the line:

sum+= A[i][k]*B[k][j]

Let's rewrite it "properly", as:

sum= sum+A[i][k]*B[k][j]

Then, in the tropical semiring, this becomes:

sum= min(sum, A[i][k]+B[k][j])

And you're done.