6.3 Transitiver Abschluß

Gegeben: G = (V,E) errichtet und unbewertet Gesucht:

Der nun folgende Algorithmus zur Bestimmung der transitiven Hülle von G ist ein typisches Beispiel für das Dynamic Programming:

Bestimme r ^k(i,j) = TRUE $\iff$$\exists$ Weg von i nach j , der nur über Knoten {1,...,k} läuft. Initial seien die r ⁰(i,j) -Werte durch r ⁰(i,j) = TRUE $\iff$(i,j) $\in$ E gegeben.

Der Algorithmus sieht dann wie folgt aus:

     FOR k := 1 TO n DO
          FOR ALL i, j DO
               r ^k(i,j) := r ^{(k - 1)}(i,j) OR ( r ^{(k - 1)}(i,k) AND r ^{(k - 1)}(k,j) )
          END;
     END;

Die Matrix (r ⁿ)_i,j ist dann das gewünschte Ergebnis.

Die Laufzeit dieses Algorithmus liegt in O(n ³) .