Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Berge-Hasse-Algorithmus aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Berge-Hasse-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 $K\_\{i,k\}=\backslash begin\{cases\}\; 0~\backslash mathrm\{falls\}~i=j\; \backslash \backslash \; c~\backslash mathrm\{falls\}~j\; \backslash in\; i\; \backslash \backslash \; \backslash infty~\backslash mathrm\{sonst\}\backslash end\{cases\}$

heißt Kostenmatrix oder Bewertungsmatrix von N .

Entfernungsmatrix

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

heißt Entfernungsmatrix von N.

F,G seien (n,n) ? Matrizen. Es sei H := F ? G mit
$h\_\{i,j\}\; =\; min\; \backslash lbrace\; f\_\{i,l\}+g\_\{l,j\}\; \backslash vert\; \backslash lbrace\; 1,....$ $\backslash rbrace\; \backslash rbrace~\backslash mathrm\{fuer\}~i,j\; \backslash in\; \backslash lbrace\; 1,....,\backslash 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

       VIDEO-NEWS UND ANGEBOTE