Floyd Warshall Algoritme

Verward om de kortste weg van uw locatie naar bestemming te kiezen?. Dan moet u weten over dit algoritme.

• Floyd-Warshall’s Algoritme wordt gebruikt om de kortste paden tussen alle paren van hoekpunten in een grafiek te vinden, waarbij elke rand in de grafiek een gewicht heeft dat positief of negatief is.
• Het grootste voordeel van het gebruik van dit algoritme is dat alle kortste afstanden tussen 2 willekeurige hoekpunten kunnen worden berekend in O(V3), waarbij V het aantal hoekpunten in een grafiek is.
• Floyd-Warshall-algoritme wordt ook wel Floyd’s algoritme, Roy-Floyd-algoritme, Roy-Warshall-algoritme of WFI-algoritme genoemd.
• Dit algoritme volgt de dynamische programmeringsaanpak om de kortste paden te vinden.

Algoritme

Voor een grafiek met N hoekpunten:

Stap 1: initialiseer de kortste paden tussen willekeurige 2 hoekpunten met Infinity.

Stap 2: vind alle paarsgewijs kortste paden die 0 tussenliggende hoekpunten gebruiken, vind dan de kortste paden die 1 tussenliggend hoekpunt gebruiken enzovoort… tot alle N hoekpunten als tussenliggende knooppunten worden gebruikt.

Stap 3: Minimaliseer de kortste paden tussen de 2 paren in de vorige operatie.

Stap 4: Voor elke 2 hoekpunten (i,j) , moet men eigenlijk de afstanden tussen dit paar minimaliseren door de eerste K knopen te gebruiken, zodat het kortste pad zal zijn: min(dist+dist,dist).

dist vertegenwoordigt het kortste pad dat alleen de eerste K hoekpunten gebruikt, dist vertegenwoordigt het kortste pad tussen het paar k,j. Aangezien het kortste pad een aaneenschakeling zal zijn van het kortste pad van i naar k, dan van k naar j.

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 );
}
}
}

Voorbeeld

Laat de gegeven grafiek zijn:

Volg de onderstaande stappen om het kortste pad te vinden tussen alle paren van hoekpunten.

1. Creëer een matrix A0 van dimensie n*n waarin n het aantal hoekpunten is. De rij en de kolom worden respectievelijk geïndexeerd als i en j. i en j zijn de hoekpunten van de grafiek.

Elke cel A wordt gevuld met de afstand van het ith hoekpunt tot het jth hoekpunt. Als er geen pad is van ith hoekpunt naar jth hoekpunt, wordt de cel als oneindig gelaten.

2. Maak nu een matrix A1 met behulp van matrix A0. De elementen in de eerste kolom en de eerste rij laten we staan zoals ze staan. De overige cellen worden op de volgende manier gevuld.

Let k op het bevriezende hoekpunt in het kortste pad van bron naar bestemming. In deze stap is k het eerste hoekpunt.A wordt gevuld met (A + A) if (A > A + A).

Dit wil zeggen, als de directe afstand van de bron naar de bestemming groter is dan het pad door het hoekpunt k, dan wordt de cel gevuld met A + A.

In deze stap, is k hoekpunt 1. We berekenen de afstand van het bronvertex naar het bestemmingsvertex door dit vertex k.

Voorbeeld: Voor A1 is de directe afstand van hoekpunt 2 tot 4 4 en de som van de afstand van hoekpunt 2 tot 4 via hoekpunt (dus van hoekpunt 2 tot 1 en van hoekpunt 1 tot 4) is 7. Aangezien 4 < 7, wordt A0 gevuld met 4.

3. Op soortgelijke wijze wordt A2 gecreëerd met behulp van A3. De elementen in de tweede kolom en de tweede rij worden gelaten zoals ze zijn.

In deze stap is k het tweede hoekpunt (d.w.z. hoekpunt 2). De overige stappen zijn dezelfde als in stap 2.

4. Op dezelfde manier worden ook A3 en A4 aangemaakt.

A4 geeft het kortste pad tussen elk tweetal hoekpunten.

Kies het kortste pad, gebruik dan onderstaande code om het te vinden. Maar voer de juiste afstanden in.

Tijdcomplexiteit

Er zijn drie lussen. Elke lus heeft een constante complexiteit. Dus de tijdcomplexiteit van het Floyd-Warshall-algoritme is O(n3).

Ruimtecomplexiteit

De ruimtecomplexiteit van het Floyd-Warshall-algoritme is O(n2).