Min-Plus-Matrixmultiplikations-Algorithmus

Algorithmus der Graphentheorie zur Ermittlung des kürzesten Pfades

Der Min-Plus-Matrixmultiplikations-Algorithmus ist ein Algorithmus der Graphentheorie, der die kürzesten Pfade eines Graphen berechnet. Er läuft mit einer speziellen Matrizenmultiplikation und hat zudem den Vorteil, dass bei jedem Berechnungsschritt automatisch alle Informationen über erreichbare Wege innerhalb der bisher angegebenen Anzahl der Berechnungsschritte verfügbar sind. Er ist allerdings sehr rechenintensiv und daher langsam.

Definitionen

Bearbeiten

Gegeben seien ein gerichteter Graph   und eine Matrix mit Gewichten  , wobei die Indizes   und   über die Menge   laufen.

Bewertungsmatrix

Bearbeiten

Die Kostenmatrix oder Bewertungsmatrix   ist dann wie folgt definiert:

 

Entfernungsmatrix

Bearbeiten

Die Entfernungsmatrix   ist wie folgt definiert

 

Matrizenoperation ⊕

Bearbeiten

  seien zwei  -Matrizen. Die Matrix   berechnet sich wie folgt:

 

wobei gelten soll  .

  ist also die Multiplikation von Matrizen über einem Halbring mit  .

Statt   schreiben wir kurz  .

 

Zusammenhang mit Kürzesten Pfaden

Bearbeiten

Für einen gerichteten Graph   mit positiven Kantengewichten   (oder mit konservativer Gewichtsfunktion) gilt:

  • Die Matrix   gibt die Länge der kürzesten Pfade mit maximal   Kanten an. Der Eintrag   gibt dabei die Länges des kürzesten Pfad (mit maximal   Kanten) von Knoten   zu Knoten   an.
  • Wenn   die Anzahl der Knoten ist dann gilt   für alle  .
  • Wenn   dann auch  .

Algorithmus

Bearbeiten

Der Min-Plus-Matrixmultiplikations-Algorithmus berechnet nun ausgehend von der Kostenmatrix   des Graph   sodass  .

Variante 1: Berechnet   bis  . Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes mit der Matrix   multipliziert.

Variante 2: Berechnet   bis  . Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.

Laufzeit

Bearbeiten

Im Folgenden verwenden wir die Landau-Notation, um das asymptotische Verhalten der Laufzeit anzugeben. Im worst case benötigt Variante 1   Matrixmultiplikationen während Variante 2 nur   Matrixmultiplikationen benötigt. Die Laufzeit mit der naiven Implementierung der Min-Plus-Matrixmultiplikation ist dann in   für Variante 1 und in   für Variante 2. Damit hat der Algorithmus eine schlechtere Laufzeit als der vergleichbare Algorithmus von Floyd und Warshall dessen Laufzeit in   ist.

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

Siehe auch

Bearbeiten