Applications
Dioids, especially the (max, +) and (min, +) dioids on the reals, are often used in performance evaluation on discrete event systems. The real numbers then are the "costs" or "arrival time"; the "max" operation corresponds to having to wait for all prerequisites of an events (thus taking the maximal time) while the "min" operation corresponds to being able to choose the best, less costly choice; and + corresponds to accumulation along the same path.
The Floyd–Warshall algorithm for shortest paths can thus be reformulated as a computation over a (min, +) algebra. Similarly, the Viterbi algorithm for finding the most probable state sequence corresponding to an observation sequence in a Hidden Markov model can also be formulated as a computation over a (max, ×) algebra on probabilities. These dynamic programming algorithms rely on the distributive property of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.
Read more about this topic: Semiring