Bewertungsmatrix

Die Kostenmatrix oder Bewertungsmatrix ${\displaystyle K}$ ist dann wie folgt definiert:

${\displaystyle k_{i,j}={\begin{cases}0~\mathrm {falls} ~i=j\\c_{i,j}~\mathrm {falls} ~(i,j)\in E\\\infty ~\mathrm {sonst} \end{cases}}}$

Entfernungsmatrix

Die Entfernungsmatrix ${\displaystyle D}$ ist wie folgt definiert

${\displaystyle d_{i,j}={\begin{cases}0,~\mathrm {falls} ~i=j\\\mathrm {L{\ddot {a}}nge~des~k{\ddot {u}}rzesten~Weges~von~} i\mathrm {~nach~} j\\\infty ,~\mathrm {falls~es~keinen~Weg~gibt} ~\end{cases}}}$

Matrizenoperation ⊕

${\displaystyle F,G}$ seien zwei ${\displaystyle n\times n}$-Matrizen. Die Matrix ${\displaystyle H=F\oplus G}$ berechnet sich wie folgt:

${\displaystyle h_{i,j}=\min\{f_{i,l}+g_{l,j}\mid l\in \{1,\dots ,n\}\}}$

wobei gelten soll ${\displaystyle a+\infty =\infty +a=\infty }$.

${\displaystyle \oplus }$ ist also die Multiplikation von Matrizen über einem Halbring mit ${\displaystyle (0,1,+,\cdot ):=(\infty ,0,\operatorname {min} ,+)}$.

Statt ${\displaystyle K\oplus K}$ schreiben wir kurz ${\displaystyle K^{[2]}}$.

${\displaystyle K^{[i+1]}=K^{[i]}\oplus K}$

Laufzeit

Im Folgenden verwenden wir die Landau-Notation, um das asymptotische Verhalten der Laufzeit anzugeben. Im worst case benötigt Variante 1 ${\displaystyle \Theta \left(n\right)}$ Matrixmultiplikationen während Variante 2 nur ${\displaystyle \Theta \left(\log n\right)}$ Matrixmultiplikationen benötigt. Die Laufzeit mit der naiven Implementierung der Min-Plus-Matrixmultiplikation ist dann in ${\displaystyle \Theta \left(n^{4}\right)}$ für Variante 1 und in ${\displaystyle \Theta \left(n^{3}\cdot \log n\right)}$ für Variante 2. Damit hat der Algorithmus eine schlechtere Laufzeit als der vergleichbare Algorithmus von Floyd und Warshall dessen Laufzeit in ${\displaystyle {\mathcal {O}}(n^{3})}$ ist.

Die Laufzeit kann jedoch durch kompliziertere Implementierungen der Min-Plus-Matrixmultiplikation verbessert werden.