Tropical Matrix Product
Replace sums and products with min-plus operations to compose weighted paths.
Free theory articleReplace sums and products with min-plus operations to compose weighted paths.
Concept & interpretation
The tropical semiring, or min-plus algebra, replaces traditional addition with taking the minimum, and traditional multiplication with ordinary addition.
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.