Min-Plus-Matrixmultiplikations-Algorithmus

Beim Berge-Hasse-Algorithmus handelt es sich um einen Kürzeste-Wege-Algortihmus, der sehr laufzeitintensiv ist. Ist aber ein sehr schönes Spielzeug für Hobbymathematiker und wird in der einen oder anderen Hochschule sogar gelehrt. Der Berge-Hasse-Algorithmus 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.

Definitionen

Bewertungsmatrix

Gegeben sei ein Netzwerk $K_{i,k}={\begin{cases}0fallsi=j\\cfallsj\in i\\\infty 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}0fallsi=j\\LaengedeskuerzestenWegesvoninachj(fallsj\in R(i))\\\infty 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 fueri,j\in \lbrace 1,....,\rbrace$