- tags
- Mathematics

## Definition

The min tropical semiring is the semiring \((\mathbb{R} \cup \{ +\infty \}, \oplus, \otimes )\) with the operations:

- \(x \oplus y = \min(x, y)\)
- \(x \otimes y = x + y\)

The unit for \(\oplus\) is \(+\infty\) and the unit for \(\otimes\) is \(0\). The max tropical semiring is defined similarly by replacing \(\min\) with \(\max\).

## Relation with shortest path algorithms

There is an interesting connection between the min tropical semiring and Dijkstra’s algorithm.

Let \(G\) the weighted graph representing a shortest path problem and \(A\) its adjacency matrix (the elements of \(A\) are the weight between the nodes, or \(+\infty\) if there is no path between two node).

For \(k \in \mathbb{N}\), coefficient \(i, j\) of the matrix \(A^k\) contains the smallest cost of all path from node \(i\) to node \(j\) with \(k\) edges. Moreover, the vector \((+\infty, +\infty, …, 0, …, +\infty)A^n\) with a \(0\) in position \(p\) is the cost from any nodes to the target node \(p\).

See these slides by Nicolas Delanoue for some more details.