Consider a graph with weights on its edges. Like the one in the

figure, for example. One way to represent this graph is via an adjacency

matrix A whose component A(s, t) is the weight of the edge between

nodes s and t. Notice that since there may not be edges

between all vertices (after all, what’s the fun in a complete graph?),

A is a partial function. We can solve

this by adjoining a value infty to the

possible weights and assigning it as the weight of the non-existent

edges. In case this solution seems like a dirty trick to you, a

possibility is to think of this process as the same as returning a

`Maybe`

value to make a partial function total, with infty playing the role of

`Nothing`

.

Given this graph, a common question to ask is what are best ways to

travel between its vertices. That is, if you want to go from node s to node t,

which sequence of edges should you choose? If you’ve read what I have been writing about dynamic

programming, you are probably already smelling the sweet scent of

*value functions* and Bellman equations in the air.

Let mathcal{S} be the (finite) set

of nodes in the graph, and let’s define V

colon mathcal{S}times mathcal{S}to (-infty, infty] as the

value function which tells us the length of the shortest path between

two vertices. With a bit of dynamic programming, we can find out that

V satisfies a Bellman equation:

begin{aligned}

V(s, s) &= 0 \

V(s, t) &= min_{q in mathcal{S}}, A(s, q) + V(q, t), ; forall

s ne t.

end{aligned}

The first line is the base case for the recursion and represents the

0-step paths. It costs nothing to just stay where you are, but it is in

turn impossible to reach any other vertex in zero steps. This may seem

really simple, but let’s nevertheless define a matrix I to represent this 0-step reachability

relation. Why we want to do that will soon be clear.

I(s, t) = begin{cases}

0 ,& s = t \

infty ,& s ne t.

end{cases}

We can use I to write the recurrence

more compactly:

V(s, t) = min left{ I(s, t),, min_{q in mathcal{S}} A(s, q) +

V(q, t) right}

What the above equation means is that the minimal distance between

two vertices is the shortest among staying in the vertex (an empty path)

and recursively following the shortest path with at least one edge.

## Every problem is linear if you squint hard

enough

The equation above is indeed rather ugly. However, by looking at it

with care, one can the structure unveiling. First, the term

min_{q in mathcal{S}}, A(s, q) + V(q, t)

looks a lot like some kind of composition where we aggregate over the

middle index q. Even more: if you

squint your eyes enough, it looks a lot like the formula for matrix

multiplication.

Well, let’s try to discover where this idea takes us. Even if it is

just for the sake of abstract nonsense, it could be interesting. In

general, when talking about real numbers, we use the usual arithmetic

structure with addition and multiplication. Today we’re going to be

eccentric and define a new kind of addition and multiplication:

begin{aligned}

a oplus b &= min{a,, b}, \

a otimes b &= a + b, \

mathbf{0} &= infty, \

mathbf{1} &= 0.

end{aligned}

So, what is happening here? The thing is: the real numbers extended

with infty satisfy all the axioms for

a Semiring

structure if we take sum to be min

and product to be +. This is called the

**min-plus** or **Tropical**

semiring and, surprisingly, satisfies a lot of the axioms we expect

from a sum and product The main difference is that instead of having

inverses, oplus is idempotent.

Before further exploring the properties of the Tropical semiring, or

of semirings in general, let’s take advantage of our new notation to

rewrite the ugly equation

V(s, t) = I(s, t) oplus bigoplus_{q in mathcal{S}} A(s, q) otimes

V(q, t)

into the much more elegant (and index-free!) matrix format

V = I oplus (A otimes V).

By now, the choice of the letter I

for the 0-step becomes clear: it is the identity matrix in the Tropical

algebra!

What is cool is that in this form, finding the shortest path becomes

the same as solving a linear system. Can we transfer the methods from

classical linear algebra to this semiring setting? Unfortunately the

answer is in general negative… This is why we will have to require a

further piece of structure from our semirings: a **closure
operator** denoted ^* which

returns the fixed point of the mapping x

mapsto mathbf{1} oplus a otimes x, that is, we require

that

x^* = mathbf{1} oplus a otimes x^* =

mathbf{1} oplus x^star otimes a.

Now, you may call me a cheater since this is the scalar version of

the shortest path equation. Nevertheless, we will see that while such an

operator tends to be pretty simple to define for the scalar field, it is

also the missing piece for solving the **Algebraic Path
Problem**. That is, an algorithm capable of solving the Bellman

equation in a way that is polymorphic on the semiring.

Alright, that was a pretty mathematical introduction. It’s far from

time for this post to become more computational. Let’s take the above

discussion to Haskell land by defining a `Semiring`

class.

Wikipedia

article on the topic.

## The Tropical Semiring

and Shortest Paths

One can think of a semiring as a structure with an operation for

combining two values (otimes) and

another for aggregating values (oplus). Since the min-plus semiring was our

choice for intuition, let’s start the implementation with it.

The semiring instance is straighforward, since the constructors

closely resemble the class methods. We will only implement a couple

simplifications in order to not get expressions with redundant

parts.

defined for

calculus expressions on another post. All of them are some kind of

“realizations of typeclass”.

The usefulness of this interpreter comes from the fact that it

commutes with the matrix operations. Thus, whenever we want to perform

many queries in a same graph with idempotent aggregations (such as

shortest paths, largest paths, most reliable paths, widest paths etc.),

we may first calculate the regular expressions representing these paths

and then collapse them separately for each semiring.

## Classical Matrix Inversion

To wrap up this post, let’s take a look at a semiring that is not

idempotent: the classical field structure on the real/complex numbers.

Or, to be technicality accurate, one of these fields complete with an

extra point to amount for the non-invertibility of zero.