algorithm
Floyd-Warshall-algoritme

All Pair Shortest Path Algorithm

Het algoritme van Floyd-Warshall is voor het vinden van de kortste paden in een gewogen grafiek met positieve of negatieve randgewichten. Een enkele uitvoering van het algoritme vindt de lengtes (opgetelde gewichten) van de kortste paden tussen alle paar hoekpunten. Met een beetje variatie kan het het kortste pad afdrukken en negatieve cycli in een grafiek detecteren. Floyd-Warshall is een algoritme voor dynamisch programmeren.

Laten we een voorbeeld bekijken. We gaan het algoritme van Floyd-Warshall op deze grafiek toepassen:

Het eerste wat we doen is, nemen we twee 2D-matrices. Dit zijn aangrenzende matrices . De grootte van de matrices wordt het totale aantal hoekpunten. Voor onze grafiek nemen we 4 * 4 matrices. De afstandsmatrix gaat de minimaal gevonden afstand tussen twee hoekpunten opslaan. Voor de randen, als er een rand is tussen uv en de afstand / gewicht is w , slaan we op: distance[u][v] = w . Voor alle randen die niet bestaan, gaan we oneindig . De padmatrix is voor het regenereren van het minimale afstandpad tussen twee hoekpunten. Dus als er een pad is tussen u en v , gaan we path[u][v] = u . Dit betekent dat de beste manier om van vertex-u naar vertex-v te komen, is door de rand te gebruiken die v met u verbindt. Als er geen pad tussen twee hoekpunten is, gaan we N daar plaatsen om aan te geven dat er nu geen pad beschikbaar is. De twee tabellen voor onze grafiek zien er als volgt uit:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  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

Omdat er geen lus is, zijn de diagonalen ingesteld op N. En de afstand vanaf het hoekpunt zelf is 0 .

Om het Floyd-Warshall-algoritme toe te passen, gaan we een middelpunt selecteren k . Vervolgens gaan we voor elk hoekpunt i controleren of we van i naar k en vervolgens van k naar j kunnen gaan , waarbij j een ander hoekpunt is en de kosten minimaliseren om van i naar j te gaan . Als de huidige afstand [i] [j] groter is dan afstand [i] [k] + afstand [k] [j] , gaan we afstand [i] [j] gelijk stellen aan de som van die twee afstanden . En het pad [i] [j] wordt ingesteld op pad [k] [j] , omdat het beter is om van i naar k te gaan en vervolgens van k naar j . Alle hoekpunten worden geselecteerd als k . We hebben 3 geneste lussen: voor k van 1 tot 4, ik van 1 tot 4 en j van 1 tot 4. We gaan het volgende controleren:

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

Dus wat we eigenlijk controleren, is dat we voor elk paar hoekpunten een kortere afstand krijgen door door een ander hoekpunt te gaan? Het totale aantal bewerkingen voor onze grafiek is 4 * 4 * 4 = 64 . Dat betekent dat we deze controle 64 keer gaan uitvoeren. Laten we er een paar bekijken:

Wanneer k = 1 , i = 2 en j = 3 , is afstand [i] [j] -2 , wat niet groter is dan afstand [i] [k] + afstand [k] [j] = -2 + 0 = -2 . Het blijft dus ongewijzigd. Nogmaals, wanneer k = 1 , i = 4 en j = 2 , afstand [i] [j] = oneindig , wat groter is dan afstand [i] [k] + afstand [k] [j] = 1 + 3 = 4 . Dus zetten we afstand [i] [j] = 4 , en we zetten pad [i] [j] = pad [k] [j] = 1 . Wat dit betekent is dat om van vertex-4 naar vertex-2 te gaan , het pad 4-> 1-> 2 korter is dan het bestaande pad. Dit is hoe we beide matrices vullen. De berekening voor elke stap wordt hier weergegeven. Na het aanbrengen van de nodige wijzigingen zien onze matrices eruit:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  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

Dit is onze kortste afstandsmatrix. De kortste afstand van 1 tot 4 is bijvoorbeeld 3 en de kortste afstand tussen 4 en 3 is 2 . Onze pseudo-code zal zijn:

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

Het pad afdrukken:

Om het pad af te drukken, controleren we de padmatrix . Om het pad van u naar v af te drukken, beginnen we vanaf pad [u] [v] . We zullen instellen dat v = pad [u] [v] blijft veranderen totdat we pad [u] [v] = u vinden en alle waarden van pad [u] [v] in een stapel pushen. Na het vinden van u, zullen wij u af te drukken en start popping items uit de stapel en afdrukken. Dit werkt omdat het pad matrix slaat de waarde van het hoekpunt waarvan deelt de kortste weg naar v van een ander knooppunt. De pseudo-code zal zijn:

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

Negatieve randcyclus vinden:

Om erachter te komen of er een negatieve randcyclus is, moeten we de hoofddiagonaal van de afstandsmatrix controleren . Als een waarde op de diagonaal negatief is, betekent dit dat er een negatieve cyclus in de grafiek is.

complexiteit:

De complexiteit van het Floyd-Warshall-algoritme is O (V³) en de complexiteit van de ruimte is: O (V²) .