Why do we need left distibutivity when using semirings for shortest-path problems?

Question

This paper describes a framework for shortest-path algorithms based on semirings. My question is, why do we need left distributivity of ⊕ (generalized sum) over ⊗ (generalized product) for the algorithms to give correct results.

In other words, why do we need the law:

a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c) 

Answer 1

The simple answer is that the paper is going to discuss algorithms that can be applied to semirings. So something has to satisfy the properties of a semiring if you want to apply them!

Typically, algorithms will make great use of the distributivity laws to manipulate summations; e.g. to invoke the identity

$$ \bigoplus_{i,j} \left( a_i \otimes b_j \right) = \left( \bigoplus_i a_i \right) \otimes \left( \bigoplus_j b_j \right) $$

---

Frequently, problems that can be phrased in terms of interesting semirings are of the sort where

• You are assembling smaller things into larger things, represented by $\otimes$
• You are aggregating things into collections, represented by $\oplus$

The distributivity law is simply expressing that you get the same result whether you do the aggregation before or after doing the combinations.

A common example is that the objects represent collections of paths in a graph. The operation $a \otimes b$ yields the collection you get by concatenating a path from $a$ with a path from $b$ in all possible ways, and the operation $a \oplus b$ means to take the union of the two collections.

Answer 2

Eh, it turns out left distributivity is not necessary. The paper says:

Our framework can also be generalized by introducing right and left semirings [28]. A right semiring is an algebraic structure similar to a semiring except that it may lack left distributivity.