Floyd-Warshall per tutte le coppie
Trovare i cammini minimi tra ogni coppia
Floyd-Warshall per tutte le coppie è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Tutte le coppie in una volta
A volte serve il cammino minimo tra ogni coppia di nodi, non solo da una singola sorgente. Questo è il problema dei cammini tra tutte le coppie.
Ecco Floyd-Warshall
Floyd-Warshall riempie una tabella completa delle distanze per tutte le coppie con tre semplici cicli annidati e quasi nessuna inizializzazione.
La matrice delle distanze
Utilizzi una matrice in cui dist[i][j] è il costo minimo conosciuto da i a j. La inizializzi usando gli archi diretti forniti.
dist = [[INF] * n for _ in range(n)]Impostare la diagonale
Ogni nodo raggiunge sé stesso gratuitamente, quindi imposti a zero la diagonale dist[i][i] prima di iniziare i rilassamenti.
for i in range(n):
dist[i][i] = 0L'idea del nodo intermedio
La tecnica consiste nel consentire ai cammini di passare attraverso un nodo intermedio k, quindi verificare se passare da k è più economico che procedere direttamente.
L'ordine dei cicli è importante
Il ciclo esterno è k, il punto intermedio scelto. I cicli interni su i e j provano ogni coppia rispetto a quel punto intermedio.
for k in range(n):
for i in range(n):
for j in range(n):Il passaggio di rilassamento
Per ogni coppia, rilassi passando da k: se il percorso da i a k e poi a j è più breve, aggiorni dist[i][j] con il costo complessivo.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]Perché k va all'esterno
Quando k termina, tutte le coppie possono usare nodi intermedi fino a k. Mettere k all'esterno mantiene corretta questa garanzia.
Gli archi negativi vanno bene
Floyd-Warshall accetta gli archi negativi, ma non i cicli negativi. Un ciclo negativo lascia una voce della diagonale minore di zero.
Il tempo di esecuzione
Tre cicli su n nodi richiedono O(n^3) tempo e O(n^2) spazio; è pratico solo quando n rimane nell'ordine di qualche centinaio.
Quando sceglierlo
Scelga Floyd-Warshall quando il grafo è piccolo e denso e servono davvero tutte le distanze tra le coppie, non quelle da una sola sorgente.
Verifica rapida
Quale ciclo deve essere quello più esterno in Floyd-Warshall?
Riepilogo: Floyd-Warshall
Inizializzi una matrice, imposti a zero la diagonale, quindi esegua i cicli k, i, j e rilassi passando da k. Cammini minimi tra tutte le coppie in O(n^3). 🧮
Domande Frequenti
La lezione «Floyd-Warshall per tutte le coppie» è gratuita?
Sì — il testo completo di «Floyd-Warshall per tutte le coppie» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Floyd-Warshall per tutte le coppie»?
Trovare i cammini minimi tra ogni coppia Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Floyd-Warshall per tutte le coppie»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Dijkstra con un heap
- BFS 0-1 con una Deque
- Bellman-Ford e archi negativi
- Floyd-Warshall per tutte le coppie