Min-Plus-Matrixmultiplikations-Algorithmus

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.

Definitionen

Bewertungsmatrix

Gegeben sei ein Netzwerk Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle K_{i,k}=\begin{cases} 0~\mathrm{falls}~i=j \\ c~\mathrm{falls}~j \in i \\ \infty~\mathrm{sonst}\end{cases}}

heißt Kostenmatrix oder Bewertungsmatrix von N .

Entfernungsmatrix

Gegeben sei ein Netzwerk N. Die (n,n) - Matrix D mit $d_{i,k}={\begin{cases}0~\mathrm {falls} ~i=j\\\mathrm {Weg~von} ~i~\mathrm {nach} ~j~\mathrm {(falls} ~j\in R(i))\\\infty ~\mathrm {sonst} ~\end{cases}}$

heißt Entfernungsmatrix von N.

F,G seien (n,n) – Matrizen. Es sei H := F ⊕ G mit $h_{i,j}=min\lbrace f_{i,l}+g_{l,j}\vert \lbrace 1,....$ $\rbrace \rbrace ~\mathrm {fuer} ~i,j\in \lbrace 1,....,\rbrace$

wobei gelten soll; a + ∞ = ∞ + a = ∞ .

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