Algoritmo di Floyd Warshall

Non riesci a scegliere il percorso più breve dalla tua posizione alla destinazione? Allora, dovresti conoscere questo algoritmo.

• L’algoritmo di Floyd-Warshall è usato per trovare i percorsi più brevi tra tutte le coppie di vertici in un grafico, dove ogni bordo nel grafico ha un peso che è positivo o negativo.
• Il più grande vantaggio di usare questo algoritmo è che tutte le distanze più brevi tra qualsiasi 2 vertici possono essere calcolate in O(V3), dove V è il numero di vertici in un grafico.
• L’algoritmo di Floyd-Warshall è anche chiamato algoritmo di Floyd, algoritmo Roy-Floyd, algoritmo Roy-Warshall, o algoritmo WFI.
• Questo algoritmo segue l’approccio di programmazione dinamica per trovare i percorsi più brevi.

Algoritmo

Per un grafico con N vertici:

Passo 1: Inizializza i percorsi più brevi tra qualsiasi 2 vertici con Infinity.

Passo 2: Trova tutte le coppie di percorsi più brevi che usano 0 vertici intermedi, poi trova i percorsi più brevi che usano 1 vertice intermedio e così via… fino ad usare tutti gli N vertici come nodi intermedi.

Passo 3: Minimizzare i percorsi più brevi tra qualsiasi 2 coppie nell’operazione precedente.

Passo 4: Per qualsiasi 2 vertici (i,j) , si dovrebbe effettivamente minimizzare le distanze tra questa coppia usando i primi K nodi, così il percorso più breve sarà: min(dist+dist,dist).

dist rappresenta il percorso più breve che usa solo i primi K vertici, dist rappresenta il percorso più breve tra la coppia k,j. Poiché il percorso più breve sarà una concatenazione del percorso più breve da i a k, poi da k a 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 );
}
}
}

Esempio

Lasciamo che il grafico dato sia:

Seguite i passi seguenti per trovare il percorso più breve tra tutte le coppie di vertici.

1. Crea una matrice A0 di dimensione n*n dove n è il numero di vertici. La riga e la colonna sono indicizzate rispettivamente come i e j. i e j sono i vertici del grafico.

Ogni cella A è riempita con la distanza dal vertice ith al vertice jth. Se non c’è un percorso dal vertice ith al vertice jth, la cella viene lasciata come infinito.

2. Ora, create una matrice A1 usando la matrice A0. Gli elementi della prima colonna e della prima riga sono lasciati come sono. Le celle rimanenti sono riempite nel modo seguente.

Lascia che k sia il vertice congelante nel percorso più breve dalla sorgente alla destinazione. In questo passo, k è il primo vertice.A viene riempito con (A + A) if (A > A + A).

Ovvero, se la distanza diretta dalla sorgente alla destinazione è maggiore del percorso attraverso il vertice k, allora la cella viene riempita con A + A.

In questo passo, k è il vertice 1. Calcoliamo la distanza dal vertice sorgente al vertice destinazione attraverso questo vertice k.

Per esempio: Per A1, la distanza diretta dal vertice 2 al 4 è 4 e la somma della distanza dal vertice 2 al 4 attraverso il vertice (cioè dal vertice 2 al 1 e dal vertice 1 al 4) è 7. Poiché 4 < 7, A0 è riempito con 4.

3. In modo simile, A2 è creato usando A3. Gli elementi della seconda colonna e della seconda riga sono lasciati come sono.

In questo passo, k è il secondo vertice (cioè il vertice 2). I passi rimanenti sono gli stessi del passo 2.

4. Allo stesso modo, vengono creati anche A3 e A4.

A4 dà il percorso più breve tra ogni coppia di vertici.

Confuso per selezionare il percorso più breve, quindi utilizzare il codice seguente per trovarlo. Ma inserisci le distanze corrette.

Complessità temporale

Ci sono tre cicli. Ogni ciclo ha complessità costante. Quindi, la complessità temporale dell’algoritmo di Floyd-Warshall è O(n3).

Complessità spaziale

La complessità spaziale dell’algoritmo di Floyd-Warshall è O(n2).