Najkratšia cesta, PSA 2
O(log2N) krokov s O(N3) procesormi
P4 nie je vhodný, ak máme N3 procesorov, pretoze ich nevyuzjeme všetky
Program P5
initially ? || i, j :: d[i, j] = W[i, j] ?
assign ? ||i, j :: d[i, j] := ? min k:: d[i, k] + d[k, j] ??
program pozostáva z jediného príkazu, ktorý priradí N2 hodnôt
po m-tom vykonaní príkazu platí nasledovný invariant:
d[i, j] je dlzka najkratšej cesty z i do j s najviac 2m?1 vrcholmi medzi i a j
dá sa ukázat, ze FP sa dosiahne po O(log N) vykonaniach príkazu „assign…“
na jedno vykonanie treba cas O(log N); ide o nájdenie minima a výpocet d[i, k] + d[k, j]
- d[i, k] + d[k, j] môze byt vypocítané na N3 procesoroch v konštantnom case
- pre dané i, j minimum cez k môze byt vypocítané v case O(log N) pomocou O(N) procesorov
teda kazdý krok mozno urobit v case O(log N) a s O(N3) procesormi
kedze výpocet má O(log N) krokov, tak program P5 vypocíta D v case O(log2N) a s O(N3) procesormi