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.


← Back to Notes