Er du forvirret over at vælge den korteste vej fra din placering til destinationen?. Så bør du kende til denne algoritme.
- Floyd-Warshalls algoritme bruges til at finde de korteste stier mellem alle par af toppunkter i en graf, hvor hver kant i grafen har en vægt, som er positiv eller negativ.
- Den største fordel ved at bruge denne algoritme er, at alle de korteste afstande mellem to vilkårlige toppunkter kan beregnes på O(V3), hvor V er antallet af toppunkter i en graf.
- Floyd-Warshall-algoritmen kaldes også Floyds algoritme, Roy-Floyd-algoritmen, Roy-Warshall-algoritmen eller WFI-algoritmen.
- Denne algoritme følger den dynamiske programmeringsmetode til at finde de korteste stier.
Algoritme
For en graf med N toppunkter:
Stræk 1: Initialiser de korteste stier mellem to vilkårlige toppunkter med uendelighed.
Stræk 2: Find alle par korteste stier, der bruger 0 mellemliggende toppunkter, find derefter de korteste stier, der bruger 1 mellemliggende toppunkt osv… indtil du bruger alle N toppunkter som mellemliggende knudepunkter.
Strin 3: Minimer de korteste stier mellem 2 vilkårlige par i den foregående operation.
Strin 4: For 2 vilkårlige hjørner (i,j) skal man faktisk minimere afstandene mellem dette par ved hjælp af de første K knuder, så den korteste sti vil være: min(dist+dist,dist).
dist repræsenterer den korteste sti, der kun bruger de første K hjørner, dist repræsenterer den korteste sti mellem parret k,j. Da den korteste vej vil være en sammenkædning af den korteste vej fra i til k, og derefter fra k til 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 );
}
}
}
Eksempel
Lad den givne graf være:
Følg nedenstående trin for at finde den korteste vej mellem alle hjørneparrene.
- Opret en matrix
A0af dimensionn*n, hvor n er antallet af toppunkter. Rækken og kolonnen er indekseret som henholdsvis i og j. i og j er toppene i grafen.
Hver celle A er udfyldt med afstanden fra toppunktet ith til toppunktet jth. Hvis der ikke er nogen vej fra ith toppunkt til jth toppunkt, efterlades cellen som uendelig.
2. Opret nu en matrix A1 ved hjælp af matrix A0. Elementerne i den første kolonne og den første række efterlades som de er. De resterende celler udfyldes på følgende måde:
Lad k være det frysende toppunkt i den korteste vej fra kilde til destination. I dette trin er k det første toppunkt.A fyldes med (A + A) if (A > A + A).
Det vil sige, at hvis den direkte afstand fra kilden til destinationen er større end vejen gennem toppunktet k, så fyldes cellen med A + A.
I dette trin er k toppunkt 1. Vi beregner afstanden fra kildepunktet til bestemmelsespunktet gennem dette punkt k.
Til eksempel: For A1 er den direkte afstand fra toppunkt 2 til 4 4 4, og summen af afstanden fra toppunkt 2 til 4 gennem toppunktet (dvs. fra toppunkt 2 til 1 og fra toppunkt 1 til 4) er 7. Da 4 < 7 er A0 fyldt med 4.
3. På lignende måde oprettes A2 ved hjælp af A3. Elementerne i den anden kolonne og den anden række forbliver som de er.
I dette trin er k det andet toppunkt (dvs. toppunkt 2). De resterende trin er de samme som i trin 2.
4. På samme måde oprettes A3 og A4 også.
A4 giver den korteste vej mellem hvert par af toppunkter.
Vil du vælge den korteste vej, skal du bruge nedenstående kode til at finde den. Men indtast de korrekte afstande.
Tidskompleksitet
Der er tre sløjfer. Hver løkke har konstante kompleksiteter. Så tidskompleksiteten af Floyd-Warshall-algoritmen er O(n3).
Rumkompleksitet
Rumkompleksiteten af Floyd-Warshall-algoritmen er O(n2).