Min-Plus-Matrix-Produkt und Min-Plus-Transitive Hülle

$$\mathbbm{R}(+ , \bullet)$$

$$\nearrow \nwarrow$$

Gruppe Halbgruppe

$$\mathbbm{N}(+ , \bullet)$$

$$\nearrow \nwarrow$$

Halbgruppe Halbgruppe

Semiring über $\mathbbm{R}\cup \{\infty\}$ mit Operationen $\min$ und +, jeweils Halbgruppe.
Distributivgesetz $a + \min\{b, c\} = \min\{a+b, a+c\}$

Normale Matrixmultiplikation:

$$\begin{split} &A = (a_{ij})_{1 \leq i,j \leq n}, \quad B = ... ..., \quad c_{ij} = \sum_{k=1}^{n}a_{ik}\cdot b_{kj} \end{split}$$

Entsprechend für Min-Plus:

$$c_{ij} = \min\{a_{ik}+b_{kj}; 1\leq k \leq n\}$$

Anwendung: A=B
kürzeste Wege von v_i nach w_j in einem Graph (A=B)

$$I_{\min, +} = \begin{pmatrix} 0 & & \infty\\ & \ddots & \\ \infty & & 0 \end{pmatrix}$$

Sei A Entfernungsmatrix, $A = (a_{ij})_{1 \leq i,j \leq n} = (\text{d}(v_i,v_j))_{1 \leq i,j \leq n}$. Setze a_ii = 0 für $i=1,\ldots ,n$.

Betrachte A² (Min-Plus-Produkt):
$A^2 = (a_{ij}^{(2)})_{1 \leq i,j \leq n}$.
Dann ist a_ij⁽²⁾ die Länge eines kürzesten Pfades von v_i nach v_j, der höchstens zwei Kanten enthält. Induktion: a_ij^(k) ist die Länge des kürzesten Pfades von v_i nach v_j mit höchstens k Kanten.
Falls die d(v_i, v_j) alle $\geq0$, gibt es immer kürzeste Pfade, die $\leq n-1$ Kanten enthalten.

Alternative Lösung des All-Pairs-Shortest-Path-Problems: Berechne A^n-1 (Min-Plus). Es genügt auch $A^{2^{\lceil\log(n-1)\rceil}}$ (nicht $A^2,A^3,A^4,\ldots$berechnen, sondern wiederholt quadrieren).

$A^* := \min_{i \geq 0}\{A^i\}$ heißt Min-Plus-Transitive Hülle.

Bemerkung: Min wird Komponentenweise gebildet. Wenn $d\geq 0$, dann A^* = A^n-1.