Najkratšia cesta, ASM 3

• Pevný bod sa dosiahne, kedze metrika ? + i, j :: k[i, j] ? sa zvýši s kazdou zmenou stavu a je ohranicená zhora.

• Program P6

  declare k: array[0..N?1, 0..N?1] of int
  
  initially ? || i, j :: d[i, j], k[i, j] = W[i, j], 0 ?
  assign {r znamená pre zjednodušenie k[i, j]}
  ?  i, j :: d[i, j], r := min(d[i, j], d[i, r] + d[r, j]), r + 1
  if r < N ? k[i, r] ? r ? k[r, j] ? r ?

end{P6}

Previous slide

Next slide

Back to first slide

View graphic version