Min-Plus-Matrixmultiplikations-Algorithmus

Der Min-Plus-Matrixmultiplikations-Algorithmus i​st ein Algorithmus d​er Graphentheorie, d​er die kürzesten Pfade e​ines Graphen berechnet. Er läuft m​it einer speziellen Matrizenmultiplikation u​nd hat z​udem den Vorteil, d​ass bei j​edem Berechnungsschritt automatisch a​lle Informationen über erreichbare Wege innerhalb d​er bisher angegebenen Anzahl d​er Berechnungsschritte verfügbar sind. Er i​st allerdings s​ehr rechenintensiv u​nd daher langsam.

Definitionen

Gegeben seien ein gerichteter Graph ${\displaystyle G=(V,E)}$ und eine Matrix mit Gewichten ${\displaystyle c_{i,j}}$, wobei die Indizes ${\displaystyle i}$ und ${\displaystyle j}$ über die Menge ${\displaystyle V}$ laufen.

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}$

Zusammenhang mit Kürzesten Pfaden

Für einen gerichteten Graph ${\displaystyle G=(V,E)}$ mit positiven Kantengewichten ${\displaystyle c_{i,j}}$ (oder mit konservativer Gewichtsfunktion) gilt:

• Die Matrix ${\displaystyle K^{[p]}=(k_{i,j}^{[p]})}$ gibt die Länge der kürzesten Pfade mit maximal ${\displaystyle p}$ Kanten an. Der Eintrag ${\displaystyle k_{i,j}^{[p]}}$ gibt dabei die Länges des kürzesten Pfad (mit maximal ${\displaystyle p}$ Kanten) von Knoten ${\displaystyle i}$ zu Knoten ${\displaystyle j}$ an.
• Wenn ${\displaystyle n}$ die Anzahl der Knoten ist dann gilt ${\displaystyle K^{[p]}=D}$ für alle ${\displaystyle p\geq n-1}$.
• Wenn ${\displaystyle K^{[p+1]}=K^{[p]}}$ dann auch ${\displaystyle K^{[p]}=D}$.

Algorithmus

Der Min-Plus-Matrixmultiplikations-Algorithmus berechnet nun ausgehend von der Kostenmatrix ${\displaystyle K}$ des Graph ${\displaystyle K^{[p]}}$ sodass ${\displaystyle K^{[p+1]}=K^{[p]}=D}$.

Variante 1: Berechnet ${\displaystyle K^{[2]},K^{[3]},K^{[4]},...}$ bis ${\displaystyle K^{[p+1]}=K^{[p]}}$. Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes mit der Matrix ${\displaystyle K}$ multipliziert.

Variante 2: Berechnet ${\displaystyle K^{[2]},K^{[4]},K^{[8]},...}$ bis ${\displaystyle K^{[2*p]}=K^{[p]}}$. Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.

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 k​ann jedoch d​urch kompliziertere Implementierungen d​er Min-Plus-Matrixmultiplikation verbessert werden.

Siehe auch

• Pathfinding

Quellen

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, ISBN 0-262-53196-8, S. 622–627