Pri algoritmu FW iščemo najkrajšo pot v
Floyd - Warshall algoritem NALOGE IN KVIZ
Floyd - Warshall algoritem NALOGE IN KVIZ
Sandra Selšek
1. vprašanje
Rešitev je pravilna.
Rešitev je napačna, pravilna rešitev je: uteženem in usmerjenem grafu.
2. vprašanje
Kaj iščemo s FW algoritmom:
Rešitev je pravilna.
Rešitev je napačna, pravilna rešitev je: vse najkrajše poti med vsemi pari točk.
3. vprašanje
Časovna zahtevnost FW algoritma je:
Rešitev je pravilna.
Rešitev je napačna, pravilna rešitev je: .
4. vprašanje
Prostorska zahtevnost FW algoritma je:
Rešitev je pravilna.
Rešitev je napačna, pravilna rešitev je: .
5. vprašanje
Rešitev za 6 točko je:
| - |
Katera narisana rešitev je pravilna?
Rešitev je pravilna.
6. vprašanje
7. vprašanje
Tabela nam prikazuje čas, v katerem prevozimo razdaljo med štirimi mesti (A, B, C, D). Upravnik podjetje v mestu D, ki se ukvarja s prevozništvom, bi rad pripeljal čim hitreje od mesta D do vseh ostalih mest. Na voljo ima poljubno tovornjakov. Koliko tovorjakov mora hkrati poslati iz podjetja, da se noben tovornjak ne bo vračal nazaj in bojo naredili najkrajšo pot?
Lahko pošlejo samo en tovornjak, pa bojo naredili najkrajšo pot, tako da bojo najprej odpeljali v mesto B, nato v mesto C in na koncu še v mesto A.
Naloga 1
Za graf z dano matriko dolžin povezav poišči najkrajše razdalje med posameznimi pari točk. Nariši še graf, ki ga matrika predstavlja!
Naloga 2
Naloga 3
Podjetje Najslajši d.o.o. ima 7 trgovin v sedmih različnih mestih. V trgovini v mestu 2 in mestu 4 imajo tudi pekarno. Vsak dan morajo iz teh dveh mest pripreljati čim hitreje najrazličnejše slastne dobrote v vsa ostala mesta. Tovornjakov imajo poljubno veliko, stroški prevoza so zanemarljivi. Čas prevoza med posameznimi mesti je v naslednji matriki. Organiziraj prevoz optimalno! Najbolje, da rezultat narišeš! Če raztovorijo tovornjak v trenutku in je nosilnost tovornjaka poljubno velika, koliko najmanj tovornjakov potrebuješ za optimalen prevoz?
Ker vemo, da ni pomembna nosilnost tovornjaka in čas raztovarjanja, lahko do optimalnega razvoza pridemo z izračunom FW algoritma. Torej ni potrebno upoštevati še dodatem čas raztovarjanja in seveda za prevoz tovora vedno uporabimo en sam tovornjak saj lahko nanj naložimo celoten tovor. Ko izvedemo FW algoritem, pridemo do grafa iz točke 2 in 4.
Iz točke 2 je razvidno optimalno s petimi tovornjaki. Preštejemo koliko končnih točk oz trgovin je na grafu. Do vsake te točke pripelje en tovornjak, seveda posamezni tovornjak ima lahko še vmesne postaje oz trgovine, na te pa ni nujno, da smo pozorni zaradi "raztovora v trenutku" in "poljubne nosilnosti tovornjaka".
Iz točke 4 vidimo da optimalni razvoz lahko naredimo s štirimi tovornjaki. spet prešejemo končne postaje.
Torej, vsak dan zjutraj mora štartati (5+4) 9 tovornjakov za najhitrejši razvoz sladic iz trgovine v mestu 2 in 4.
Naloga 4
V občini Vsi Čudni s petimi mesti so imeli tradicijo, da so vsak 1. maj vsi prišli v mesto 5. Razdalje med temi petimi mesti so v spodnji matriki. V mestu so vse poti enosmerne. Največja družina je v mestu 5, ta družina mora izdelati posebno okrašene palice iz lipovega lesa, ki jih mora pokazati vsem družinam po vseh ostalih mestih. Vsako mesto je moralo videti vsaj eno poalico, ta palica pa je morala iz mesta 5 potovati po najkrajši možni poti. Koliko palic mora izdelati največja družina? Kako dolgo pot mora prepotovati posamezna palica?
Uporabimo FW algoritem ,saj vemo da bomo tako izračunali vse najkrajše poti iz vseh možnih mest. Nato pa si narišemo samo graf iz točke oz mesta 5.
Iz grafa je jasno razvidna rešitev po kateri nas sprašuje naloga. Koliko palic mora izdelati družina, preštejemo tako da preštejemo končna mesta oz točke. Torej mora izdelati 3 palice. Prva palica bo potovala iz mesta 5 v mesto 1 in nato v mesto 3. Prepotovala bo (2+3) 5 razdalj. Druga palica bo potovala iz mesta 5 v mesto 1 in nato v mesto 4. Prepotovala bo (2+2) 4 razdalj. Tretja palica pa bo potovala iz mesta 5 v mesto 2. Prepotovala bo 7 razdalj.
Naloga 5
Poiščite najkrajše poti iz točke 3 do vseh ostalih točk. Narišite drevo najkrajših povezav z utežmi.
Naloga 6
Fotograf si je ogledal 6 prelepih krajev za fotografiranje. Zapisal si je km med kraji v spodnjo matriko. Pomagaj mu najti najkrajši čas potovanja s Floyd-Warshallovim postopkom. Povej koliko dni bo potreboval, da bo slikal vse kraje, če je doma na kraju številka 3 in če se bo ob vsakem prihodu domov spočil in prenočil eno noč? Koliko km bo naredil v eno smer posamezni dan?
Potreboval bo 3 dni. Prvi dan bo šel na kraj 5 in nato kraj 1 in naredil bo (3+3) 6km. Drugi dan bo šel na kraj 4 in nato na kraj 6. Naredil bo (6+5) 11km. Tretji dan pa na kraj 2 in naredil 4km.
Naloga 7
Poiščite najkrajše poti med vsemi pari točk! Uporabite algoritem Floyd-Warshall. Prek katerih točk poteka najkrajša pot iz 4 do 7?
