9.3 Shortest Path

Gegeben: Gerichteter Graph G = (V,E) , gewichtet mit Kostenfunktion.
Gesucht: Kürzester Weg von x zu allen anderen Knoten.

Idee von Moore:

Initialisiere d[i] : = $\infty$ für alle Knoten i ; d[x] : = 0 ; d bezeichnet die vorläufige Weglänge.
Es wird eine Schlange verwendet, die solche Knoten enthält, die noch zur Verbesserung beitragen können.

enqueue(s,x);
WHILE NOT emptyqueue(s) DO
   u := front(s); dequeue(s);
   FOREACH Nachbar v von u DO
      tmp := d[u] + c[u,v];
      IF tmp < d[v] THEN
         d[v] := tmp;
         IF v ist nicht in Schlange s
            THEN enqueue (s,v)
         END
      END
   END
END

A B C D E Schlange

$$\infty \infty \infty \infty$$ 0 A

$$\infty \infty$$ 0 9 4 BC

$$\infty$$ 0 9 4 11 CE

0 9 4 7 11 ED

0 9 4 7 11 D

0 8 4 7 11 BE

0 8 4 7 10 E

0 8 4 7 10

Parallele Version des Moore -Algorithmus für p Prozessoren, shared memory

enqueue (Q,x);
WHILE NOT emptyqueue (Q) DO
     FOR ALL 0 $\leq$ i $\leq$ p - 1 DO IN PARALLEL
     P_i :      hole Menge von Knoten Q _i aus der Schlange Q
         und bearbeite jedes Element aus Q _i einmal
         Ergebnis ist Schlange Q '_i
         Gliedere Q '_i in Q ein
     END
END

Menge Q ist gespeichert in

VAR Q : ARRAY [0..max-1] OF INTEGER;

Q[i] > 0 => Q[i] ist Knotenname
Q[i] < 0 => -Q[i] ist Index für Array-Element.

Knotennamen und Verweise im Array

Prozessor i bildet sein Q_i , indem er, beginnend bei Position i , jedes p -te Arrayelement aufsammelt (dabei bei negativen Einträgen dem Zeiger folgt). Q_i' wird, beginnend bei Position s_i , hintereinander abgespeichert in Q . Hinter dem letzten Knoten von Q'_i folgen p Verweise auf die ersten p Elemente der Menge Q'_{i + 1} . Jeder Prozessor hat dieselbe Anzahl ( $\pm$ 1 ) von Knoten zu bearbeiten.

Schlange Q mit Q₀ = {3,5,9,7,15},Q₁ = { 4,1,2,6}, Q₂ = {10,8,11,4}

Obacht:
VAR d: ARRAY [0..n-1] OF INTEGER (* vorläufige Distanzen *)
VAR inqueue: ARRAY [0..n-1] OF BOOLEAN (* Knoten in Schlange *)
sind global zugreifbar. Hierdurch entsteht ein Synchronisationsproblem.

tmp = d[u] + c[u,v] = 22 => d[v] := 22
tmp = d[w] + c[w,v] = 24 => d[v] := 24
Das Update von v auf 22 geht verloren.

Also: lock d[v]; tmp := d[u] + c [u,v]; IF tmp < d[v] THEN d[v] := tmp END; unlock d[v];

Analog: lock in_queue[x]; ... unlock in_queue[x];