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
werden nachgereicht
Algorithmus
1. sei die Kostenmatrix des Netzwerkes N
2. Berechne Fehler beim Parsen (Syntaxfehler): {\displaystyle K^[^2^], K^[^3^], K^[^4^], ...} gilt irgendwan Fehler beim Parsen (Syntaxfehler): {\displaystyle K^\[p+1\] = K^\[p\]} , so ist Fehler beim Parsen (Syntaxfehler): {\displaystyle K^\[p]=D}
oder
2. Berechne Fehler beim Parsen (Syntaxfehler): {\displaystyle K^\[2\], K^\[4\], K^\[8\], ...} gilt irgendwan Fehler beim Parsen (Syntaxfehler): {\displaystyle K^\[2*p\] = K^\[p\]} , so ist Fehler beim Parsen (Syntaxfehler): {\displaystyle K^\[p]=D}
Beispiel
wird nachgereicht