Floyd Warshall Algorithm

MedioCammini minimi Programmazione dinamica

+10

Un grafo orientato con n nodi, numerati da 0 a n-1, è rappresentato da una matrice n per n: matrix[i][j] è il peso dell'arco dal nodo i al nodo j, oppure -1 quando non esiste alcun arco, e matrix[i][i] è 0. La lunghezza di un percorso è la somma dei pesi dei suoi archi.

Restituisci una matrice n per n la cui voce [i][j] è la lunghezza del percorso più breve dal nodo i al nodo j, oppure -1 quando il nodo j non è raggiungibile dal nodo i.

Funzione

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: i pesi degli archi: matrix[i][j] è il peso dell’arco da i a j, oppure -1 quando non esiste
Restituisceinteger-2d-array: la distanza minima per ogni coppia di nodi, -1 quando non esiste un percorso

Vincoli

1 ≤ n ≤ 100, dove n = matrix.length = matrix[i].length
matrix[i][i] = 0
Per i ≠ j, matrix[i][j] è -1 (nessun arco) oppure 0 ≤ matrix[i][j] ≤ 1000.
I archi sono unidirezionali: matrix[i][j] e matrix[j][i] sono indipendenti.

Esempi

Input: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Output: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Spiegazione: Attraverso il nodo 1, il nodo 0 raggiunge il nodo 2 con costo 6 invece di 11, e il nodo 3 con costo 9. Il nodo 1 raggiunge il nodo 0 passando per il nodo 2 con costo 3. Dal nodo 3 non parte nulla, quindi il suo valore sulla riga è -1 fuori dalla diagonale.

Input: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Output: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Spiegazione: L’arco da 2 a 1 ha peso 0, quindi 0 → 2 → 1 ha costo 1, inferiore al 6 diretto. Nessun arco esce dal nodo 1 né entra nel nodo 0, quindi quelle coppie restano -1.

Per approfondire

Dopo aver costruito la tabella, un arco diventa meno costoso. Riesci ad aggiornare ogni distanza in O(n²) invece di eseguire di nuovo i cicli O(n³)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ti serve il percorso più breve per ogni coppia di nodi. Floyd-Warshall trova tutte le n² risposte con un unico triplo ciclo. A ogni iterazione i percorsi possono passare per un nodo in più e si esegue un confronto per ogni coppia: il percorso migliore trovato finora contro quello che passa per il nuovo nodo.

Estendi ogni percorso di un arco finché non cambia più nulla

Corretto, ma non termina sui test più grandi

Intuizione

Parti dalla matrice e, a ogni passaggio, estendi ogni percorso di un arco: un percorso da i a m più l’arco m → j è un percorso da i a j, mantenuto se è più breve. Ripeti finché un passaggio non modifica nulla.

Dopo p passaggi, viene trovato ogni percorso più breve composto da un massimo di p+1 archi. Nessun peso è negativo, quindi un percorso più breve non contiene cicli e ha al massimo n-1 archi; i passaggi si interrompono con tutte le distanze definitive. Un passaggio richiede n³ = 10^6 operazioni per 100 nodi, e una lunga catena di percorsi più brevi richiede fino a n passaggi: O(n⁴), fino a 10^8 operazioni.

Algoritmo

Copia matrix in dist.
Per ogni i, m e j: se dist[i][m] e matrix[m][j] esistono entrambi, calcola la loro somma.
Se dist[i][j] è -1 o maggiore della somma, memorizza la somma e ricorda che il passaggio ha modificato qualcosa.
Ripeti il passaggio finché non modifica più nulla, poi restituisci dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: consenti una fermata in più a ogni iterazione

Intuizione

Limita i nodi in cui un percorso può fermarsi tra i suoi estremi. La tabella inizialmente è la matrice, cioè i percorsi senza fermate. Dopo il turno k, dist[i][j] è il percorso più breve le cui fermate si trovano tutte tra i nodi da 0 a k, e l’ultimo turno fornisce la risposta.

Nel turno k, il percorso migliore che può fermarsi anche in k o salta k, e la tabella lo contiene già, oppure passa per k una volta, poiché nessun peso è negativo. Le sue due metà si fermano solo nei nodi da 0 a k-1, quindi sono dist[i][k] e dist[k][j].

Nel primo esempio, il turno 1 sostituisce il percorso diretto di 11 dal nodo 0 al nodo 2 con un percorso di 6. Il turno 2 dà un percorso dal nodo 0 al nodo 3 pari a 6 + 3 = 9, con la fermata nel nodo 1 all’interno del tratto di 6.

Basta una sola tabella: la riga k e la colonna k non cambiano nel turno k, perché dist[k][k] è 0.

Algoritmo

Copia matrix in dist; -1 significa che non è ancora stato trovato alcun percorso.
Per k da 0 a n-1, e per ogni i e j: salta la coppia se dist[i][k] o dist[k][j] è -1.
Altrimenti calcola via = dist[i][k] + dist[k][j].
Se dist[i][j] è -1 o maggiore di via, impostalo a via.
Restituisci dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Trappole e casi limite

Aggiungere -1 come se fosse un peso: -1 + 5 = 4 sembra un percorso. Controlla prima entrambe le parti e considera un -1 in dist[i][j] peggiore di qualsiasi percorso.
Inserire il ciclo su k all'interno. I percorsi attraverso le fermate da 0 a k-1 devono essere definitivi prima che venga preso in considerazione il nodo k.
Usare il valore int più grande come infinito: sommandone due si verifica un overflow di un int a 32 bit, che diventa una distanza negativa. Una distanza reale è al massimo 99 × 1000 = 99,000, quindi 10^9 è sicuro, poiché 2 × 10^9 è inferiore a 2^31-1.
Supporre che gli archi vadano in entrambe le direzioni. Nel secondo esempio, il nodo 0 raggiunge il nodo 1, ma dal nodo 1 non si raggiunge nessun altro nodo.
Eseguire una ricerca in ampiezza, che ignora i pesi: nel primo esempio indica una distanza di 11 dal nodo 0 al nodo 2, non 6.

Domande frequenti3

Qual è la complessità temporale dell'algoritmo Floyd-Warshall?

Tempo O(n³) per n nodi: tre cicli annidati sui nodi, con un'addizione e un confronto per passaggio, 10^6 passaggi per 100 nodi. Lo spazio è O(n²) per la tabella delle distanze, che può essere aggiornata sul posto.

Floyd Warshall funziona con pesi negativi degli archi?

Sì, purché non ci sia un ciclo negativo, cioè un ciclo i cui pesi sommati danno un valore inferiore a 0. In presenza di un ciclo negativo, i cammini minimi non sono definiti, e la tabella lo mostra: alcuni dist[i][i] terminano con un valore inferiore a 0.

Quando dovresti usare Floyd Warshall invece dell’algoritmo di Dijkstra?

Usa Floyd-Warshall per ogni coppia di nodi in un grafo denso con fino a qualche centinaio di nodi. Dijkstra da ogni nodo costa O(n³) con un array e O(n · E log n) con un heap, risultando più efficiente nei grafi sparsi di grandi dimensioni. Floyd-Warshall non ha bisogno di un heap e accetta archi negativi, cosa che Dijkstra non fa.

def shortestDistances(matrix):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Output atteso

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]