algorithm
Floyd-Warshall algoritm

Alla par kortaste sökväg algoritm

Floyd-Warshalls algoritm är för att hitta kortaste vägar i en vägd graf med positiva eller negativa kantvikter. En enda exekvering av algoritmen hittar längderna (summerade vikter) för de kortaste vägarna mellan alla vertikala par. Med lite variation kan den skriva ut den kortaste vägen och kan upptäcka negativa cykler i en graf. Floyd-Warshall är en dynamisk programmeringsalgoritm.

Låt oss titta på ett exempel. Vi kommer att tillämpa Floyd-Warshalls algoritm på den här grafen:

Det första vi gör är att vi tar två 2D-matriser. Det här är adjacensmatriser . Storleken på matriserna kommer att bli det totala antalet toppningar. För vår graf tar vi 4 * 4 matriser. Distansmatrisen kommer att lagra det minsta avstånd som hittills hittats mellan två toppar. Först, för kanterna, om det finns en kant mellan uv och avståndet / vikten är w , kommer vi att lagra: distance[u][v] = w . För alla kanter som inte finns, kommer vi att sätta oändlighet . Path Matrix är avsedd för regenerering av minsta distansväg mellan två vertikaler. Så till en början, om det finns en väg mellan u och v , kommer vi att sätta path[u][v] = u . Detta betyder att det bästa sättet att komma till vertex-v från vertex-u är att använda kanten som förbinder v med u . Om det inte finns någon bana mellan två hörn, kommer vi att lägga N där som indikerar att det inte finns någon bana nu. De två tabellerna för vår graf kommer att se ut:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Eftersom det inte finns någon slinga ställs diagonalerna in N. Och avståndet från själva toppunktet är 0 .

Att tillämpa Floyd-Warshall algoritm, vi kommer att välja en medelväg vertex k. Sedan för varje hörn i, kommer vi att kontrollera om vi kan gå från i till k och sedan k till j, där j är en annan vertex och minimera kostnaden för att gå från i till j. Om det aktuella avståndet [i] [j] är större än avståndet [i] [k] + avståndet [k] [j] , kommer vi att sätta avståndet [i] [j] lika med summeringen av dessa två avstånd . Och vägen [i] [j] kommer att ställas in på sökväg [k] [j] , eftersom det är bättre att gå från i till k , och sedan k till j . Alla vertikaler kommer att väljas som k . Vi har tre kapslade öglor: för k går från 1 till 4, jag går från 1 till 4 och j går från 1 till 4. Vi ska kolla:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Så vad vi i grund och botten kontrollerar är att för varje vertikala par får vi ett kortare avstånd genom att gå igenom en annan toppunkt? Det totala antalet operationer för vår graf är 4 * 4 * 4 = 64 . Det betyder att vi kommer att göra denna kontroll 64 gånger. Låt oss titta på några av dem:

När k = 1 , i = 2 och j = 3 , är avståndet [i] [j] -2 , vilket inte är större än avståndet [i] [k] + avståndet [k] [j] = -2 + 0 = -2 . Så det kommer att förbli oförändrat. Återigen, när k = 1 , i = 4 och j = 2 , avstånd [i] [j] = oändlighet , vilket är större än avståndet [i] [k] + avstånd [k] [j] = 1 + 3 = 4 . Så vi lägger avstånd [i] [j] = 4 , och vi lägger väg [i] [j] = sökväg [k] [j] = 1 . Vad detta betyder är att gå från topp-4 till topp-2 är vägen 4-> 1-> 2 kortare än den befintliga vägen. Så här fyller vi båda matriserna. Beräkningen för varje steg visas här . Efter att vi har gjort nödvändiga ändringar ser våra matriser ut:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Detta är vår kortaste distansmatris. Till exempel är det kortaste avståndet från 1 till 4 3 och det kortaste avståndet mellan 4 till 3 är 2 . Vår pseudokod kommer att vara:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Skriva ut sökvägen:

För att skriva ut sökvägen, kontrollerar vi sökvägsmatrisen . För att skriva ut banan från u till v , börjar vi från sökväg [u] [v] . Vi kommer att ställa in att fortsätta ändra v = sökväg [u] [v] tills vi hittar sökväg [u] [v] = u och skjuter alla värden på sökväg [u] [v] i en bunt. Efter att ha hittat dig , kommer vi att skriva ut u och börja poppa objekt från bunten och skriva ut dem. Detta fungerar eftersom den bana matris lagrar värdet av vertex som delar den kortaste vägen till v från någon annan nod. Pseudokoden kommer att vara:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Hitta negativ kantcykel:

För att ta reda på om det finns en negativ kantcykel måste vi kontrollera huvuddiagonalen för distansmatris . Om något värde på diagonalen är negativt betyder det att det finns en negativ cykel i diagrammet.

Komplexitet:

Komplexiteten hos Floyd-Warshall-algoritmen är O (V³) och rymdkomplexiteten är: O (V²) .