Min-Plus-Matrixmultiplikations-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 | Quelltext bearbeiten]

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

Bewertungsmatrix[Bearbeiten | Quelltext bearbeiten]

Die Kostenmatrix oder Bewertungsmatrix ist dann wie folgt definiert:

Entfernungsmatrix[Bearbeiten | Quelltext bearbeiten]

Die Entfernungsmatrix ist wie folgt definiert

Matrizenoperation ⊕[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Quellen[Bearbeiten | Quelltext bearbeiten]