Najkratšia cesta 2: stratégia
Špecifikácia: program má pocítat maticu d tak, ze
invariant FP ? (d = D)
true ? FP
Stratégia neformálne:
- nech d[i, j] je dlzka nejakej cesty z vrcholu i do j
- ak nájdeme cestu kratšej dlzky l (cize l < d[i, j]), tak potom d[i, j] := l
- konkrétne ak ?k také, ze d[i, k] + d[k, j] < d[i, j], tak cesta cez vrchol k je kratšia
- d[i, j] := min { d[i, j], d[i, k] + d[k, j] | 0 ? k < N}
- nešpecifikujeme
- ako vyberáme i, j, k
- kedy sa operácie vykonávajú
- ktoré procesory ich vykonávajú