Floyd Warshallin algoritmi

Epäonnistutko lyhimmän reitin valitsemisessa sijainnistasi määränpäähän?. Sitten sinun pitäisi tietää tästä algoritmista.

• Floyd-Warshallin algoritmia käytetään lyhimpien polkujen löytämiseen graafin kaikkien kärkiparien välillä, jossa jokaisella graafin reunalla on paino, joka on positiivinen tai negatiivinen.
• Tämän algoritmin suurimpana etuna on se, että kaikki lyhimmät etäisyydet minkä tahansa kahden kärkipisteen välillä voidaan laskea ajassa O(V3), jossa V on graafin kärkipisteiden lukumäärä.
• Floyd-Warshall-algoritmia kutsutaan myös nimellä Floydin algoritmi, Roy-Floyd-algoritmi, Roy-Warshall-algoritmi tai WFI-algoritmi.
• Algoritmi noudattaa dynaamista ohjelmointimenetelmää löytääkseen lyhimmät polut.

Algoritmi

Graafille, jossa on N kärkeä:

Vaihe 1: Alusta lyhimmät polut minkä tahansa kahden kärkipisteen välillä äärettömällä.

Vaihe 2: Etsi kaikki parin lyhimmät polut, jotka käyttävät 0 välikärkipistettä, sen jälkeen etsi lyhimmät polut, jotka käyttävät 1 välikärkipistettä jne… kunnes käytät kaikkia N kärkipistettä välikärkipisteenä.

Vaihe 3: Minimoidaan lyhimmät polut minkä tahansa kahden parin välillä edellisessä operaatiossa.

Vaihe 4: Minkä tahansa kahden kärkipisteen (i,j) osalta pitäisi itse asiassa minimoida tämän parin väliset etäisyydet käyttäen ensimmäisiä K:ta solmua, joten lyhin polku on: min(dist+dist,dist).

dist edustaa lyhintä polkua, joka käyttää vain ensimmäisiä K:ta kärkipistettä, dist edustaa lyhintä polkua parin k:n,j:n välillä. Koska lyhin polku on lyhimpien polkujen i:stä k:hon ja sitten k:sta j:ään yhdistelmä.

for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}

Esimerkki

Asettele annettu graafi:

Seuraa alla olevia vaiheita löytääksesi kaikkien kärkipisteiden välisten kärkiparien välisen lyhimmän polun.

1. Luo matriisi A0, jonka ulottuvuus on n*n, jossa n on kärkien lukumäärä. Riviä indeksoidaan i ja saraketta j. i ja j ovat graafin kärkipisteet.

Jokaiseen soluun A merkitään etäisyys ith kärkipisteestä jth kärkipisteeseen. Jos ith-pisteestä jth-pisteeseen ei ole polkua, solu jätetään äärettömäksi.

2. Luodaan nyt matriisin A0 avulla matriisi A1. Ensimmäisen sarakkeen ja ensimmäisen rivin elementit jätetään ennalleen. Loput solut täytetään seuraavalla tavalla:

Olkoon k lähdöstä määränpäähän kulkevan lyhimmän polun jäätävä huippu. Tässä vaiheessa k on ensimmäinen piste.A täytetään solulla (A + A) if (A > A + A).

Jos suora matka lähteestä määränpäähän on suurempi kuin polku pisteen k kautta, solu täytetään solulla A + A.

Tässä vaiheessa k on piste 1. Lasketaan etäisyys lähdepisteestä kohdepisteeseen tämän pisteen k kautta.

Esim: A1:n suora etäisyys pisteestä 2 pisteeseen 4 on 4 ja pisteestä 2 pisteen kautta (eli pisteestä 2 pisteeseen 1 ja pisteestä 1 pisteeseen 4) kulkevien etäisyyksien summa on 7. Koska 4 < 7, A0 täytetään 4:llä.

3. Vastaavalla tavalla A2 luodaan A3:n avulla. Toisen sarakkeen ja toisen rivin elementit jätetään ennalleen.

Tässä vaiheessa k on toinen huippu (eli huippu 2). Loput vaiheet ovat samat kuin vaiheessa 2.

4. Samalla tavalla luodaan myös A3 ja A4.

>A4 antaa lyhimmän polun kunkin kärkiparin välillä.

Voit valita lyhimmän polun, niin käytä alla olevaa koodia sen etsimiseen. Syötä kuitenkin oikeat etäisyydet.

Aikakompleksisuus

Tässä on kolme silmukkaa. Jokaisella silmukalla on vakiot monimutkaisuudet. Floyd-Warshallin algoritmin aikakompleksisuus on siis O(n3).

Tilakompleksisuus

Floyd-Warshallin algoritmin tilakompleksisuus on O(n2).