Min-Plus-Matrixmultiplikations-Algorithmus

Beim Berge-Hasse-Algorithmus handelt es sich um einen Kürzeste-Wege-Algorithmus. 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 $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

• Huckert/Braun/De Angelis/De Angelis: Informatik II (Graphentheorie)-Skript