- 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.