# Tropical semiring

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.

Last changed | authored by