"jliikumiseks" - 1 õppematerjal

Diskreetse matemaatika elemendid

Tõestus o Korrektsuse teoreemi võib sõnastada nii: Iga n korral kehtib: kui n on graafi tippude arv, siis Floyd-Warshalli algoritm annab etapi n tulemuseks maatriksi, kus aij on lühima tee pikkus tipust i tippu j . Sisemise väite tõestamiseks asendame ta parameetrist k sõltuva väitega: o Lemma. Etapi k (0kn) järel on aij lühima sellise tee pikkus, kus tipust i tippu jliikumiseks võib läbida vahetippe 1, … , k . Selge, et k = n puhul saame siit algoritmi korrektsuse. 45  Lemma 1 tõestame induktsiooniga k järgi. o Lemma. Etapi k (0kn) järel on aij lühima sellise tee pikkus, kus tipust i tippu j liikumiseks võib läbida vahetippe 1, … , k . o Tõestame induktsiooniga k järgi. o Induktsiooni baas. Kui k =0 , siis on lemma väide tõene.