Floyd Warshall Algoritm

Var du förvirrad när du ska välja den kortaste vägen från din plats till din destination? Då bör du känna till denna algoritm.

• Floyd-Warshalls algoritm används för att hitta de kortaste vägarna mellan alla par av hörn i en graf, där varje kant i grafen har en vikt som är positiv eller negativ.
• Den största fördelen med att använda denna algoritm är att alla de kortaste avstånden mellan två hörn kan beräknas på O(V3), där V är antalet hörn i grafen.
• Floyd-Warshalls algoritm kallas också Floyds algoritm, Roy-Floyd-algoritmen, Roy-Warshall-algoritmen eller WFI-algoritmen.
• Algoritmen följer den dynamiska programmeringsmetoden för att hitta de kortaste vägarna.

Algoritm

För en graf med N hörn:

Steg 1: Initialisera de kortaste vägarna mellan två hörn med oändlighet.

Steg 2: Hitta alla pars kortaste vägar som använder 0 mellanliggande hörn, hitta sedan de kortaste vägarna som använder 1 mellanliggande hörn och så vidare … tills du använder alla N hörn som mellanliggande noder.

Steg 3: Minimera de kortaste vägarna mellan två par i föregående steg.

Steg 4: För två hörn (i,j) bör man faktiskt minimera avstånden mellan dessa par genom att använda de första K noderna, så den kortaste vägen blir: min(dist+dist,dist).

dist representerar den kortaste vägen som endast använder de första K hörnen, dist representerar den kortaste vägen mellan paret k,j. Eftersom den kortaste vägen kommer att vara en sammanfogning av den kortaste vägen från i till k och sedan från k till 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 );
}
}
}

Exempel

Låt den givna grafen vara:

Följ nedanstående steg för att hitta den kortaste vägen mellan alla hörnpar.

1. Skapa en matris A0 med dimensionen n*n där n är antalet hörn. Raden och kolumnen indexeras som i respektive j. i och j är grafenas hörn.

Varje cell A fylls med avståndet från hörnet ith till hörnet jth. Om det inte finns någon väg från ith vertex till jth vertex lämnas cellen som oändlig.

2. Skapa nu en matris A1 med hjälp av matris A0. Elementen i den första kolumnen och den första raden lämnas som de är. De återstående cellerna fylls på följande sätt.

Låt k vara den frysta vertexen i den kortaste vägen från källa till destination. I detta steg är k den första vertexen.A fylls med (A + A) if (A > A + A).

Det vill säga, om det direkta avståndet från källan till destinationen är större än vägen genom vertexen k, fylls cellen med A + A.

I detta steg är k vertex 1. Vi beräknar avståndet från källpunkten till destinationspunkten genom denna punkt k.

Till exempel: För A1 är det direkta avståndet från vertex 2 till 4 4 och summan av avståndet från vertex 2 till 4 genom vertex (dvs. från vertex 2 till 1 och från vertex 1 till 4) är 7. Sedan 4 < 7 fylls A0 med 4.

3. På liknande sätt skapas A2 med hjälp av A3. Elementen i den andra kolumnen och den andra raden lämnas som de är.

I detta steg är k den andra vertexen (dvs. vertex 2). De återstående stegen är desamma som i steg 2.

4. På samma sätt skapas också A3 och A4.

A4 ger den kortaste vägen mellan varje par av hörn.

Var du förvirrad för att välja den kortaste vägen kan du använda nedanstående kod för att hitta den. Men ange rätt avstånd.

Tidskomplexitet

Det finns tre slingor. Varje slinga har konstant komplexitet. Så tidskomplexiteten för Floyd-Warshall-algoritmen är O(n3).

Rymdkomplexitet

Rymdkomplexiteten för Floyd-Warshall-algoritmen är O(n2).