9.4 All Shortest Paths

Gegeben: Gerichteter Graph G = (V,E) , gewichtet mit Kostenfunktion.
Gesucht: Matrix D mit d[i,j] = Länge des kürzesten Weges von i nach j .
Betrachte D ^k = d ^k[i,j] = Länge des kürzesten Weges von i nach j , der höchstens k Kanten benutzt.

Die Berechnung der Matrix D ^k geschieht analog zur Matrizenmultiplikation. Statt multipliziert wird addiert, statt addiert wird minimiert.

Verknüpfung von Zeile i mit Spalte j

Zur Berechnung von D ⁿ sind log n Matrixverknüpfungen erforderlich (gemäß Hornerschema):
Sei Binärdarstellung von n = n_{k - 1}n_{k - 2}...n₀ .

E := 1;
FOR j := k - 1 DOWNTO 0 DO
     E := E $\oplus$ E;
     IF n_j = 1 THEN E := E $\oplus$ C END
END

Also können n ³ Prozessoren auf dem Hypercube in O($\log^{2}_{}$n) alle kürzesten Wege eines n -elementigen Graphen bestimmen.