Min-Plus-Matrixmultiplikations-Algorithmus

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht signifikant verbessert werden können. Bitte hilf mit und beteilige dich an der Diskussion!

Der Berge-Hasse-Algorithmus ist ein Algorithmus der Graphentheorie, der die Distanzmatrix eines Graphen berechnet. Er läuft mit einer speziellen Matrizenoperation 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. Benannt wurde er nach Claude Berge und Helmut Hasse.

Definitionen

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

Bewertungsmatrix

Die Kostenmatrix oder Bewertungsmatrix $K$ ist dann wie folgt definiert:

$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 $D$ ist wie folgt definiert

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

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

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

wobei gelten soll $a+\infty =\infty +a=\infty$.

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

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

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

Algorithmus

1. $K$ sei die Kostenmatrix des Netzwerkes N

2. Berechne $K^{[2]},K^{[3]},K^{[4]},...$ gilt irgendwann $K^{[p+1]}=K^{[p]}$, so ist $K^{[p]}=D$

oder

2. Berechne $K^{[2]},K^{[4]},K^{[8]},...$ gilt irgendwann $K^{[2*p]}=K^{[p]}$, so ist $K^{[p]}=D$

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