Tappa
Coppie accorciate
Coppie esaminate

  • Tappa attuale
  • Già una tappa
  • Coppia accorciata
  • Percorso
Un clic su un nodo imposta

Di più sull'algoritmo di Floyd–Warshall

Algoritmo di Floyd–Warshall

Quanto dista ogni città da tutte le altre? Floyd–Warshall risponde in un colpo solo, con una tabella e tre cicli annidati. Ogni turno ammette un nodo in più come tappa e chiede, per ogni coppia, se la deviazione da lì è più breve. Procedi passo per passo per vedere la tabella riempirsi e le distanze scendere. Premi Avvia per guardare la tabella riempirsi, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. La tabella contiene la distanza più breve trovata finora tra ogni coppia di nodi; il numero su ogni arco è la sua lunghezza. Ogni turno ammette un nodo in più come tappa lungo il percorso, e ogni passo mostra una coppia che si accorcia passando da lì. Fai clic su un nodo per farne la partenza; passa il clic su Arrivo e fai clic su un altro nodo per vedere alla fine il percorso più breve tra i due. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi.
  2. Osserva la tabella: la riga e la colonna della tappa attuale sono colorate, e ogni passo scrive una distanza più breve.
  3. Scegli una partenza e un arrivo per vedere alla fine il percorso più breve tra i due. Nuovo grafo crea un altro grafo da provare.

Come funziona Floyd–Warshall

Prepara una tabella con una riga e una colonna per nodo. Scrivi 0 sulla diagonale, la lunghezza dell'arco dove due nodi sono collegati, e infinito ovunque altrove. Poi prendi a turno ogni nodo k come possibile tappa. Per ogni coppia i, j confronta la distanza da i a j nella tabella con la distanza da i a k più la distanza da k a j, e tieni la minore. Dopo l'ultimo nodo, ogni casella è la distanza più breve tra i suoi due nodi.

Perché funziona

Dopo il turno di k, la tabella contiene, per ogni coppia, il percorso più breve le cui tappe sono tutte tra i nodi trattati finora. Il turno del nodo successivo deve solo decidere se quel nodo aiuta: un percorso più breve che passa da lì è un percorso più breve fino a lì più un percorso più breve da lì, entrambi già nella tabella. Questo modo di costruire una risposta grande da risposte più piccole già trovate si chiama programmazione dinamica. Con archi negativi funziona ancora, e un numero negativo sulla diagonale rivela un ciclo negativo.

Domande frequenti

Che cos'è l'algoritmo di Floyd–Warshall?

Un algoritmo che trova la distanza più breve tra ogni coppia di nodi in un grafo pesato. Tiene una tabella delle distanze e, per ogni nodo a turno, controlla se passare da quel nodo accorcia qualche coppia.

Quanto è veloce Floyd–Warshall?

Ha tre cicli annidati sugli n nodi, quindi il lavoro cresce con n³, e la tabella richiede n² caselle. Va bene per grafi di qualche centinaio di nodi. Per grafi grandi e sparsi è più veloce eseguire l'algoritmo di Dijkstra da ogni nodo.

Floyd–Warshall gestisce gli archi negativi?

Sì, purché non ci sia un ciclo negativo. Se c'è, qualche casella sulla diagonale diventa negativa, ed è così che Floyd–Warshall lo scopre.

Come ottengo i percorsi, non solo le distanze?

Tieni una seconda tabella con il nodo successivo sul percorso da i a j. Ogni volta che una coppia si accorcia passando da k, copia il nodo successivo da i verso k. Seguendo quella tabella da i a j si ricostruisce il percorso.

Il mio grafo viene inviato da qualche parte?

No. Il grafo viene creato e la tabella riempita nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor