algorithm
Algoritmo di Floyd-Warshall

Algoritmo di percorso più breve di tutte le coppie

L'algoritmo di Floyd-Warshall è per la ricerca di percorsi più brevi in ​​un grafico ponderato con pesi di bordo positivi o negativi. Una singola esecuzione dell'algoritmo troverà le lunghezze (pesi sommati) dei percorsi più brevi tra tutte le coppie di vertici. Con una piccola variazione, può stampare il percorso più breve e può rilevare cicli negativi in ​​un grafico. Floyd-Warshall è un algoritmo di programmazione dinamica.

Diamo un'occhiata a un esempio. Applicheremo l'algoritmo di Floyd-Warshall su questo grafico:

La prima cosa che facciamo è prendere due matrici 2D. Queste sono matrici di adiacenza . La dimensione delle matrici sarà il numero totale di vertici. Per il nostro grafico, prenderemo 4 * 4 matrici. La Distance Matrix sta per memorizzare la distanza minima trovata finora tra due vertici. All'inizio, per i bordi, se c'è un margine tra uv e la distanza / peso è w , memorizzeremo: distance[u][v] = w . Per tutti i bordi che non esistono, metteremo l' infinito . La Path Matrix serve a rigenerare il percorso di minima distanza tra due vertici. Quindi, inizialmente, se v'è un percorso tra u e v, stiamo andando a mettere path[u][v] = u . Questo significa che il modo migliore per arrivare a vertice-v da vertice-u è usare il bordo che connette v con u . Se non ci sono percorsi tra due vertici, inseriremo N indicando che non esiste alcun percorso disponibile ora. Le due tabelle per il nostro grafico saranno simili a:

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

Poiché non vi è alcun loop, le diagonali sono impostate N. E la distanza dal vertice stesso è 0 .

Per applicare l'algoritmo di Floyd-Warshall, selezioneremo un vertice medio k . Quindi, per ogni vertice i , controlleremo se possiamo passare da i a ke poi da k a j , dove j è un altro vertice e minimizzare il costo di passare da i a j . Se la distanza attuale [i] [j] è maggiore della distanza [i] [k] + distanza [k] [j] , metteremo la distanza [i] [j] uguale alla somma di queste due distanze . E il percorso [i] [j] sarà impostato su path [k] [j] , poiché è meglio passare da i a k , e quindi da k a j . Tutti i vertici saranno selezionati come k . Avremo 3 cicli annidati: per k che va da 1 a 4, i che va da 1 a 4 e j che va da 1 a 4. Stiamo andando controllo:

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

Quindi quello che stiamo fondamentalmente controllando è, per ogni coppia di vertici, otteniamo una distanza più breve passando da un altro vertice? Il numero totale di operazioni per il nostro grafico sarà 4 * 4 * 4 = 64 . Ciò significa che stiamo andando a fare questo controllo 64 volte. Diamo un'occhiata ad alcuni di loro:

Quando k = 1 , i = 2 e j = 3 , la distanza [i] [j] è -2 , che non è maggiore della distanza [i] [k] + distanza [k] [j] = -2 + 0 = -2 . Quindi rimarrà invariato. Di nuovo, quando k = 1 , i = 4 e j = 2 , distanza [i] [j] = infinito , che è maggiore della distanza [i] [k] + distanza [k] [j] = 1 + 3 = 4 . Quindi inseriamo la distanza [i] [j] = 4 e inseriamo il percorso [i] [j] = percorso [k] [j] = 1 . Ciò significa che, per passare dal vertice-4 al vertice-2 , il percorso 4-> 1-> 2 è più corto del percorso esistente. Questo è il modo in cui popoliamo entrambe le matrici. Il calcolo per ogni passaggio è mostrato qui . Dopo aver apportato le modifiche necessarie, le nostre matrici saranno simili a:

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

Questa è la nostra matrice di distanza più breve. Ad esempio, la distanza più breve da 1 a 4 è 3 e la distanza più breve tra 4 e 3 è 2 . Il nostro pseudo-codice sarà:

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

Stampa del percorso:

Per stampare il percorso, controlleremo la matrice Path . Per stampare il percorso da u a v , inizieremo dal percorso [u] [v] . Continueremo a cambiare v = path [u] [v] finché non troviamo path [u] [v] = u e spingere tutti i valori di path [u] [v] in uno stack. Dopo aver trovato u, noi lo stamperemo u e cominciamo popping elementi dalla pila e stamparli. Questo funziona perché la matrice del percorso memorizza il valore del vertice che condivide il percorso più breve per v da qualsiasi altro nodo. Lo pseudo-codice sarà:

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

Individuazione del ciclo del bordo negativo:

Per scoprire se c'è un ciclo di bordo negativo, dovremo controllare la diagonale principale della matrice delle distanze . Se qualsiasi valore sulla diagonale è negativo, significa che c'è un ciclo negativo nel grafico.

Complessità:

La complessità dell'algoritmo di Floyd-Warshall è O (V³) e la complessità spaziale è: O (V²) .