Tropical Matrix Product

The tropical semiring, or min-plus algebra, replaces traditional addition with taking the minimum, and traditional multiplication with ordinary addition.

Worked Example

Consider a small adjacency matrix where 0 is on the diagonal and edges have some weights. Let's multiply a matrix A by itself using tropical arithmetic.

Since a \oplus b = min(a, b) and a \otimes b = a + b, the tropical dot product of two vectors is \min_k (a_k + b_k).

Start with matrix A, which represents distances between nodes.
A² = A \otimes A. Element (i, j) is \min_k (A_ik + A_kj).
This computes the shortest path between i and j taking exactly (or at most, with loops) 2 steps.
For instance, if A_01 = 2 and A_12 = 3, and no direct path A_02 exists (Infinity), then (A²)_02 = min(A_01 + A_12) = 2 + 3 = 5.

Experiment

In this Tropical Matrix Product module, you can see how paths are computed bounded by step counts.

Select the Graph control and choose "Path".
Set the Power to 2. This bounds our search to paths of at most 2 edges.
Set From to 0 and To to 2.
Observe the computed Distance is 5.
Change the Graph to "Cycle". The distance between 0 and 2 changes due to the new edges forming a tighter bound.

Limitations

This module shows powers up to k=3, demonstrating bounded walks. If the graph contains negative cycles, the bounded walk distance remains finite and correct for that specific step bound, but the theoretical unconstrained shortest path would be negative infinity (which is not computable via simple bounded powers if the bound doesn't exceed the number of vertices). Additionally, this doesn't replace Dijkstra or Bellman-Ford as a general purpose shortest path solver for large graphs.

References

The mathematical properties and semiring structure are well-documented. You can read more about tropical semirings in the SageMath documentation:
SageMath: Tropical Semiring

Tropical Matrix Product