Računalništvo 2

Na vaja bomo ponovili Floyd Warshallov algoritem in nato reševali naloge (na tablo) na to temo.

1) Kaj računa in kako deluje Floyd Warshallov algoritem? Kakšna je časovna zahtevnost?

2) Za spodnji graf izračunaj vse najkrajše poti s pomočjo Floyd Warshalovega algoritma:

Nato dodamo vozlišče 10 in povezavo (5 -> 10) z utežjo -1 in (10 -> 6) z utežjo 2. Kako uporabil prejšnje rezultate, da bi izračunal nove najkrajše poti?

3) Na predavanjih ste poleg izračuna matrike D(n) izračunali tudi P(n). Kaj lahko iz njih razberemo? Kako dobimo najkrajšo pot med i in j?

4) Ali imamo v omrežju lahko več najkrajših poti med dvema vozliščema? Kaj FW naredi v tem primeru? Konstruiraj graf, ki ima ogromno najkrajših poti. Bi lahko preštel vse take poti?

5) Kako bi s FW algoritmom odkrili, če v grafu obstajajo negativni cikli? Kaj vrne FW, če graf vsebuje negativen cikel?

6) Uteži sedaj dodamo še na vozlišča. Kako bi sedaj poiskal vse najkrajše poti?