Iščemo vse najkrajše poti med vsemi pari točk. Točke so v uteženem in usmerjenem grafu.

NAJKRAJŠA POT je tista pot, ki predstavlja najmanjšo (oz. najcenejšo) vsoto povezav med vozlišči grafa.

Primer uteženega grafa.

Primer uteženega in usmerjenega grafa.

Iščemo najkrajše poti v uteženem grafu $G=(V,E)$ s podano funkcijo $w: E -> R$ množice reanih števil. Ta funkcija določi strošek povezave (oz. vrednost uteži) med vsemi pari vozlišč (oz. točk) v grafu $G$.

Predpostavili bomo, da ni negativnih ciklov!

NEGATIVNI CIKEL je krožna pot, katerega vsota vrednosti povezav, ki v tem ciklu nastopajo, je negativna.

POT je enostavni sprehod, v katerem se niti točke, niti povezave ne ponovijo.

Negativni cikel, si lahko ogledamo na spodnjem primeru:

Torej: IŠČEMO VSE NAJKRAJŠE POTI MED VSEMI PARI TOČK.

Postopek, ki ga uporabljamo je Floyd-Warshallov postopek.

Floyd-Warshallov postopek lahko prikažemo s Floyd-Warshallov algoritmom, ki je primer dinamičnega programiranja.

Leta 1959 je prvič objavil ta algoritem Bernard Roy. Priznan in objavljen pa je bil ponovno leta 1962, napisala sta ga Robert Floyd in Stephen Warshallov.

Floyd-Warshallov algoritem primerja vse možne poti skozi graf med vsemi pari točk.

Za najlažje reševanje si vedno graf predstavimo v matriki. V matriko vpišemo vse vrednosti povezav med vsemi pari točk.

Kot rezultat Floyd-Warshallov algoritem vrne matriko z najkrajšimi povezavami(vrednostmi) med pari točk in pomožno matriko s najkrajšimi potmi med pari točk.

Rešitev Floyd-Warshallovega algoritma (najkrajših možnih poti med vsemi pari točk) je lahko več.

Imamo graf $G$ z vozlišči V, vsako vozišče je oštevilčeno od 1 do n.

Računamo najkrajšo pot od $i$ do $j$ z uporabo točk iz nabora $\{1,2,...,k\}$ kot vmesno točko te poti. Naš cilj je najti najkrajšo pot od vsakega $i$ za vsak $j$ z uporablanjem točk od $1$ do $k+1$.

$d_{i j}^{(k+1)}= min\{d_{i j}^{(k)}, d_{i k+1}^{(k)} + d_{k+1 j}^{(k)}\}$

$k+1$ nastopa: $d_{i k+1}^{(k)} + d_{k+1 j}^{(k)}$

$k+1$ ne nastopa: $d_{i j}^{(k)}$

Tako izračunamo vse razdalje za pare točk $(i,j)$ za $k=1, k=2, ... k=n$.

Našli smo najkrajšo pot za vse $(i,j)$ pare z uporabo kakršnih koli vmesnih točk.

V uteženem grafu $G$ s poljubnimi utežmi c iščemo vse najkrajše poti (med vsemi pari točk). Uteži so podane v matriki $C$; če med točkama ni povezave, utež (element matrike) postavimo na $\infty$.

Floyd-Warshall(G)

$D^{0}=C$
    za k=1 do |V(G)|
        za i=1 do |V(G)| //po vrsticah
            za k=1 do |V(G)| //po stolpcih

$d_{i j}^{(k)}= min\{d_{i j}^{(k-1)}, d_{i k}^{(k-1)} + d_{k j}^{(k-1)}\}$

Podano imamo matriko povezav grafu:

Pričnemo z reševanjem, na začetku si podano matriko označimo s $ω0$ in si ustvarimo pomožno matriko $π0$.

Števila v $ω0$ na mestu $dij$ nam povedo, koliko je vrednost uteži direktne povezave iz točke $i$ v točko $j$. Pri spreminjanju $ω0$ v $ω1$, $ω1$ v $ω2$, ... $ω5$ v $ω6$ spreminjamo vrednosti v primer, ko najdemo manjšo vrednost uteži povezave preko vmesne točke.

V matriko $π0$ smo vstavili začetne povezave.

V prvo vrstico smo napisali število ena na mesta, kjer obstaja direktna povezava iz točke ena do točke, kjer stoji števka ena.(V našem primeru iz točke ena pridemo v točko tri, pet in šest. Zato na teh mesti stoji število ena v prvi vrstici.)

Na isti način smo vpisali števiko dva v drugo vrstico, števiko tri v tretjo vrstico ...

Kjer smo napisali črtice, vemo da povezave iz točke i v točko j ni.

Pri spreminjanju števil v $π0$ v $π1$, $π1$ v $π2$,... $π5$ v $π6$ na mestu $dij$ spreminjamo pot iz točke $i$ v točko $j$ preko točke $k$, preko katere smo našli najkrajšo pot.

1. korak:

V matriki $ω0$ si za lažje računanje označimi prvo vrstico in prvi stolpec.

Sedaj začenm primerjati povezave med seboj.

Najprej preverilo povezave za točko 1 (za k=1):(primerjamo povezave, ki so obkrožene oranžno)

Ko pride do primera: $dij > dik + dkj$ podatek spremenimo. Torej spremenimo podatek, če najdemo pot, ki je krajša (oz. vrednost uteži je manjša) od direktne poti iz točke $i$ v točko $j$. Ta pot bo potekala skozi točko $k$.

Ko pride do primera $dij < dik + dkj$ podatek NE spremenimo. Ker je direktna pot od točke i do točke j krajša (oz. vrednost uteži je manjša), kot pot preko točke k, potdatek ne spremenimo.

Po prvem koraku ugotovimo, da se spremnijo vrednosti povezav na $d35$ in $d65$ (obkroženo modro).

Direktna pot ima iz točke 3 v točko 5 vrednost 8. Vrednost poti iz točke 3 v točko 1 je 1 in vrednost poti iz točke 1 v točko 5 je 1. (1+1=2) Torej, če gremo preko točke 1 je vrednost poti 2. Zato smo spremenili vrednost v matriki na mestu $d35$. Namesto vrednosti 8 smo napisali vrednost 2.

Direktna pot ima iz točke 6 v točko 3 neskončno vrednost(oz. ta pot ne obstaja). Vrednost poti iz točke 6 v točko 1 je 24 in vrednost poti iz točke 1 v točko 5 je 1. (24+1=25) Torej, če gremo preko točke 1 je vrednost poti 25. Zato smo spremenili vrednost v matriki na mestu $d35$. Našli smo pot z vrednostjo 25.

V matriki$ω0$ smo preverili, če obstaja kakšna krajša pot preko točke 1. Našli smo dve takšni poti ($d35$ in $d65$). Napisali smo novo matriko $ω1$, s spremenjenimi vrednostmi v $d35$ in $d65$.

Spremenimo pa tudi matriko $π0$ v matriko $π1$. Spremenile so se iste povezave ($d35$ in $d65$) kot v $ω0$. Na mesta $d35$ in $d65$ bomo napisali število 1, ki nam bo povedalo, da je najkrajša povezava preko točke 1.

Torej vrednost v matriki $π1$ na mestu $ij$ spremenimo, zato ker smo našli krajšo pot, kot pa je direktna pot od $i$ do $j$.

2. korak:

Preverimo povezave za točko 2 (za k=2).

Ko pride do primera: $dij > dik + dkj$ podatek spremenimo.

Ko pride do primera $dij < dik + dkj$ podatek NE spremenimo.

Po drugem koraku ugotovimo, da se spremni vrednost povezav na $d56$.

Direktna pot ima iz točke 5 v točko 6 vrednost 8. Vrednost poti iz točke 5 v točko 2 je 1 in vrednost poti iz točke 2 v točko 6 je 1. (1+1=2) Torej, če gremo preko točke 2 je vrednost poti 2. Zato smo spremenili vrednost v matriki na mestu $d56$. Namesto vrednosti 8 smo napisali vrednost 2.

Dobimo novo matriko $ω2$.

Spremenimo pa tudi matriko $π1$ v matriko $π2$. Na mestu $d56$ bomo napisali število 2, ki nam bo povedalo, da je najkrajša povezava preko točke 2.

Korak 3:

Preverimo povezave za točko 3 (za k=3).

Ko pride do primera: $dij > dik + dkj$ podatek spremenimo.

Ko pride do primera $dij < dik + dkj$ podatek NE spremenimo.

Po tretjem koraku ugotovimo, da se spremnijo vrednosti povezav na $d12$, $d14$, $d16$, $d21$, $d24$, $d41$, $d42$, $d45$, $d46$, $d51$, $d61$, $d62$ in $d65$.

• Direktna pot ima iz točke 1 v točko 2 neskončno vrednost(oz. ta pot ne obstaja). Vrednost poti iz točke 1 v točko 3 je 7 in vrednost poti iz točke 3 v točko 2 je 12. (7+12=19) Torej, če gremo preko točke 3 je vrednost poti 19. Zato smo spremenili vrednost v matriki na mestu $d12$. Našli smo pot z vrednostjo 19.

• Direktna pot ima iz točke 1 v točko 4 neskončno vrednost(oz. ta pot ne obstaja). Vrednost poti iz točke 1 v točko 3 je 7 in vrednost poti iz točke 3 v točko 4 je 9. (7+9=16) Torej, če gremo preko točke 3 je vrednost poti 16. Zato smo spremenili vrednost v matriki na mestu $d14$. Našli smo pot z vrednostjo 16.

• Direktna pot ima iz točke 1 v točko 6 vrednost 18. Vrednost poti iz točke 1 v točko 3 je 7 in vrednost poti iz točke 3 v točko 6 je 9. (7+9=16) Torej, če gremo preko točke 3 je vrednost poti 16. Zato smo spremenili vrednost v matriki na mestu $d16$. Namesto vrednosti 18 smo napisali vrednost 16.

...

Dobimo novo matriko $ω3$.

Spremenimo pa tudi matriko $π2$ v matriko $π3$. Na mesta $d12$, $d14$, $d16$, $d21$, $d24$, $d41$, $d42$, $d45$, $d46$, $d51$, $d61$, $d62$ in $d65$ bomo napisali število 3, ki nam bo povedalo, da je najkrajša povezava preko točke 3.

Izvedemo še korak 4, 5 in 6.

Po zadnjem šestem koraku dobimo:

V matriki $ω6$ so zapisane najmanjše uteži med posameznimi pari točk. Na mestu $dij$ je število, ki nam pove koliko je najmanjša vrednost uteži, ki jo potrebujemo da pridemo iz točke $i$ v točko $j$.

V matriki $π6$ pa so zapisane najkrajše povezave. Na mestu $dij$ v je napisana točka preko katere poteka najkrajša pot iz točke $i$ v točko $j$.

Matriki $ω6$ in $π6$ sta naš rezultat.

Sedaj moramo samo še razbrati vse najkrajše poti.

Primer: Hočemo narisati graf vseh najkrajših poti iz točke 4 do vseh ostalih točk.

Vzamemo 4 vrstico iz matrike $ω6$ in $π6$.

Kar označimo:

Najprej narišemo točke, med točkami narišemo povezave s pomočjo $π$: 3 5 4 – 3 3.

Kako?

Iz točke 4 v točko 3.

Iz točke 3 v točko 1, 5 in 6.

Iz točke 5 v točko 2.

Nato na povezave napišemo vrednosti s pomočjo matrike $ω6$ ali s pomočjo d: 2 10 1 0 9 10.

Kako s pomočjo 4 vrstice v matriki $ω6$?

Iz točke 4 v točko 3. Vrednost povezave je 1.

Iz točke 3 v točko 1. Vrednost povezave je 2-1=1.

Iz točke 3 v točko 6. Vrednost povezave je 10-1=9.

Iz točke 3 v točko 5. Vrednost povezave je 9-1=8.

Iz točke 5 v točko 2. Vrednost povezave je 10-9=1.

Kako s pomočjo matrike $ω6$?

Ko imamo že narisan graf, v matriki $ω6$ najdemo povezave med posameznimi točkami in jih napišemo na povezeve na grefu.

V našem primeru najdemo:

Dobimo Graf, ki potek iz točke 4 v vse ostale točke, po najkrajših možnih poteh.

ČASOVNA ZAHTEVNOST

Računamo zaporedje $n$ matrik $(i,j,1),(i,j,2)...(i,j,n)$ skupno število operacij je $n*2*n^{2}=2*n^{3}$.

Zato je zahtevnost algoritma: $O(|V|^{3})$

PROSTORSKA ZAHTEVNOST

Pri računanju k-te matrike je dovolj poznati le (k-1)-ov matriko D. Pravzaprav lahko sproti popravljamo vrednosti v začetni matriki; pri tem potrebujemo še nekaj dodatnega prostora. Torej je prostorska zahtevnost $O(|V|^{2})$.

Iščemo najkrajše poti med vsemi pari točk! Razdalje med točkami so prikazane v spodnji matriki.

Postopek reševanja si lahko ogledate na prikazanem filmčku.