Tropical Algebra
Tropical (min-plus) semiring: a ⊕ b = min(a,b), a ⊗ b = a+b. Matrix powers = shortest paths!
Weight Matrix W (edge weights, ∞ = no edge)
Click edge on graph to edit | ∞ = no direct edge
Compute W^⊗k (Tropical Powers)
Random Weights
Reset
Tropical Power W
⊗k
= All-Pairs Shortest Paths
k =
1
−k
+k
Show Floyd-Warshall
Tropical semiring (ℝ∪{∞}, ⊕, ⊗):
a ⊕ b = min(a, b) (addition)
a ⊗ b = a + b (multiplication)
0̃ = ∞ 1̃ = 0
(A⊗B)_ij = ⊕_k (A_ik ⊗ B_kj)
= min_k (A_ik + B_kj)
W^⊗n = dist(i,j) for n≥n-1
(Bellman-Ford in matrix form!)