Olgu Floydi-Warshalli algoritm realiseeritud nagu eelnevas, st tsüklid
on üle indeksite k , i , j ning kauguste maatriks on d .

Märgi kõik laused, mis on kauguste maatriksi d elementide kohta kindlasti tõesed.

Question

Olgu Floydi-Warshalli algoritm realiseeritud nagu eelnevas, st tsüklid
  on üle indeksite  k ,  i ,  j  ning kauguste maatriks on  d .

Märgi kõik laused, mis on kauguste maatriksi  d  elementide kohta kindlasti tõesed.

Answer

Kui lühim suunatud ahel tipust  i  tippu  j  on kaar  i  →  j , siis elemendi  d[i][j]  väärtus algoritmi käigus ei muutu.

Answer

Kui lühim ahel tipust  i  tippu  j  läbib mingit tippu  k , siis pärast
  algoritmi töö lõppu kehtib  d[i][k] + d[k][j] == d[i][j] .

Answer

Kui elemendi  d[i][j]  väärtus jääb pärast kogu algoritmi täitmist samaks,
  siis ei leidu graafis ahelat tipust  i  tippu  j .

Crowdly