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. Benannt wurde er nach Claude Berge und Helmut Hasse.

Inhaltsverzeichnis

Definitionen

Gegeben seien ein gerichteter Graph G = (V,E) und eine Matrix mit Gewichten ci,j, wobei die Indizes i und j über die Menge V laufen.

Bewertungsmatrix

Die Kostenmatrix oder Bewertungsmatrix K ist dann wie folgt definiert:

k_{i,j}=\begin{cases} 0~\mathrm{falls}~i=j \\ c_{i,j}~\mathrm{falls}~ (i,j) \in E \\ \infty~\mathrm{sonst}\end{cases}

Entfernungsmatrix

Die Entfernungsmatrix D ist wie folgt definiert

d_{i,j}=\begin{cases} 0,~\mathrm{falls}~i=j \\ 
\mathrm{L\ddot ange~des~k\ddot urzesten~Weges~von~} i \mathrm{~nach~} j\\ 
\infty,~\mathrm{falls~es~keinen~Weg~gibt}~\end{cases}

Matrizenoperation ⊕

F,G seien zwei n\times n-Matrizen. Die Matrix H = F \oplus G berechnet sich wie folgt:

h_{i,j} = \min \{ f_{i,l}+g_{l,j} \mid l \in \{ 1,\dots,n \}\}

wobei gelten soll a + \infty = \infty + a = \infty.

Statt K \oplus K schreiben wir kurz K[2].

K^{[n+1]}=K^{[n]} \oplus K

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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Distanzmatrix — Die Distanzmatrix zeigt die Abstände, d. h., die Anzahl der Bindungen zwischen den Atomen eines Moleküls an. Die Distanzmatrix beschreibt damit einen wichtigen Aspekt der Topologie einer chemischen Verbindung. Das Molekül wird dabei als… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”