Najkratšia cesta, SA
najjednoduchšie na sekvencnej architektúre: vykonat N3 priradení cez 3 cykly (i, j, k), kde i, j bezí rýchlejšie ako k
kazdý príkaz sa vykoná práve raz
uvazujme cesty z i do j, v ktorých indexy vrcholov, co sa na týchto cestách nachádzajú, sú menšie nez k okrem koncových vrcholov i, j; nech H[i, j, k] je minimálna dlzka takýchto ciest
Teoréma:
? ?i, j:: H[i, j, 0] = W[i, j] ? ?
? ?i, j, k:: H[i, j, k +1] =
min(H[i, j, k], H[i, k, k] + H[k, j, k]) ?
Dôkaz. Uvazujme cestu, ktorá dosahuje práve minimum H[i, j, k +1]
- ak k nie je v tejto ceste, tak H[i, j, k +1] = H[i, j, k]
- ak k je v tejto ceste, tak H[i, j, k +1] = H[i, k, k] + H[k, j, k]
Podla definície d[i, j] = H[i, j, N] (vrcholy sú 0..N?1)
Teoréma: Mnozina rovností (4) je “proper”.
Dôkaz.
- kazdé H[i, j, k] je na lavej strane práve raz
- rovnice usporiadame tak, ze k bude neklesajúce
program P2:
- O(N3) rovností
- O(N3) pamäte a casu