I have a problem where I have a graph (directed or undirected) and want to compute its transitive closure. As it turns out, what I want is the length of paths between two nodes. So, “distance” in the standard and classic form. But I wondered: if we think of distance as a property of paths, then it’s got a certain structure to it:
imagine that distance is a label on an edge.
then running warshall’s algorithm, each time you add a new edge from i->j due to there being an edge i->k and an edge k->j, you add the labels on the two edges.
But also, if there’s already such an edge, then you take the min of the labels of the two putative edges, as being the label for the edge.
So there’s addition, and then this min operation. It feels like there’s some sort of nice mathematical structure just out-of-reach, and maybe even other examples of two such operations, that would allow warshall’s algorithm to be applied to compute other functions on graphs.
But then again, maybe this is just a brain-fart, and I should be happy I can compute my graph-distances with such ease.
This reminds me of work on algebraic structures underlying “routing protocols” by mathematically-minded networking people. (One can think of routing as a sort of proof-relevant distance, we care not only about distance but about the path taken. Routing people also consider many cost metrics that have worse properties than distances.) I discovered this area through talks of Timothy G. Griffin, but there is a rich tradition starting well before. I would look at his Metarouting paper from 2005 with ̃Jao Luís Sobrinho to get a sense of this community, and find pointers to related work if it piques your curiosity.
The mathematical structure you’re looking for is Kleene Algebra, the algebra of regular expressions.
A Kleene Algebra is an idempotent semiring with an iteration operator, usually denoted as *.
Dexter Kozen’s lecture notes on Kleene Algebra explain the connection to all-pairs shortest paths. The semiring in that case is the “tropical semiring”, the Kleene Algebra is simply called min,+ Kleene Algebra.
Here is a paper that is dedicated to this connection (though I haven’t read it myself).
EDIT: Let me say briefly how the structure you observed map to Kleene Algebra – see the sources linked above for more details:
Label on edges → n-by-n matrix over label set K, where the label set forms a Kleene Algebra (K, 0, 1, +, x, *), n is the number of vertices, and M_i,j = label on edge from i to j (0 if there is no edge).
Composing labels → x (not +) from the Kleene Algebra K
Selecting labels → + from the Kleene Algebra
One iteration of the algorithm → matrix multiplication
Taking the transitive closure → * from the Kleene Algebra K^nxn – if K is a Kleene Algebra, so is the set K^nxn of n-by-n matrices over K