Algoritmo Floyd-Warshall: guida all'intervista alla codifica

TL;DR: L'algoritmo Floyd-Warshall calcola i percorsi più brevi di tutte le coppie con programmazione dinamica. Inizializza una matrice di distanza dal grafico, quindi per ogni vertice intermedio k aggiorna ciascuna coppia con dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Funziona nel tempo O(V³) e nello spazio O(V²) e può esporre cicli negativi tramite voci diagonali negative.

Cos'è l'algoritmo Floyd-Warshall?

Floyd-Warshall è un algoritmo di programmazione dinamica per i percorsi più brevi tra ogni coppia ordinata di vertici. Funziona con grafici ponderati diretti o non orientati e consente bordi negativi. Se esiste un ciclo di peso negativo rilevante, tuttavia, alcuni percorsi più brevi non hanno un minimo finito perché attraversare ripetutamente il ciclo continua a ridurre il costo del percorso.

L'algoritmo è memorabile perché trasforma un problema di percorso globale in un'unica decisione: per l'attuale vertice intermedio k, il percorso più noto da i a j è migliore così com'è, o andando da i a k e poi da k a j?

Come si ricava la ricorrenza?

Definiamo D(k, i, j) come la distanza più breve da i a j i cui vertici intermedi possono provenire solo dai primi k vertici. Un percorso minimo consentito evita il vertice k, mantenendo D(k−1, i, j), oppure utilizza k e si divide nel miglior percorso consentito da i a k ​​più il miglior percorso consentito da k a j.

Ciò dà la ricorrenza:

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

Poiché lo stadio k dipende solo dai valori dello stadio k−1 in modo compatibile, la matrice può essere aggiornata sul posto. Questo ragionamento spiega anche l'ordine del ciclo critico: k deve essere il ciclo più esterno. Mettere i o j all'esterno modifica l'invariante e può utilizzare in modo errato percorsi parzialmente consentiti.

Come si inizializza la matrice delle distanze?

Crea una matrice V per V. Imposta dist[i][i] su zero, imposta la cella di un bordo diretto sul suo peso e usa infinito quando non esiste alcun bordo diretto. Se sono possibili bordi paralleli, mantenere il peso diretto più piccolo. Prima di aggiungere due distanze, verificare che entrambe siano finite in modo che una sentinella dell'infinito non trabocchi o crei un falso candidato.

Come rintracciare Floyd-Warshall in un'intervista?

Etichetta le righe della matrice come origini e le colonne come destinazioni. Mostra la matrice iniziale, quindi scegli un k e valuta le celle rappresentative. Per ogni cella, confronta il valore corrente con il percorso attraverso k. Aggiorna solo quando entrambi i segmenti sono raggiungibili e la nuova somma è inferiore.

Normalmente non è necessario disegnare ogni matrice per un esempio di grandi dimensioni. Traccia un numero sufficiente di celle per dimostrare l'invariante, incluso un miglioramento e un valore invariato. Dichiariamo che dopo aver completato k, ogni voce della matrice è ottimale tra percorsi i cui vertici intermedi sono limitati all'insieme elaborato.

Quale pseudocodice dovresti scrivere?

Usa tre cicli nidificati con k all'esterno:

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Spiegare i controlli finiti e il tipo numerico. Nelle lingue con una grande sentinella intera, aggiungere infinito a un valore negativo può sembrare finito o traboccare. Una guardia è parte della correttezza, non semplicemente un dettaglio implementativo.

Quali sono le complessità temporali e spaziali?

I tre cicli esaminano ogni combinazione di k, ie j, quindi il runtime è O(V³). La matrice delle distanze occupa lo spazio O(V²). L'aggiornamento sul posto evita una tabella tridimensionale, mentre una matrice dell'hop successivo o predecessore per la ricostruzione del percorso aggiunge O(V²) più spazio.

Floyd-Warshall è spesso interessante per grafi modesti e densi perché la sua implementazione è compatta e prevedibile. Per un grafico sparso di grandi dimensioni con archi non negativi, eseguire Dijkstra da ciascuna origine può essere più efficiente. Confronta sempre l'output richiesto, la densità del grafico, i vincoli di peso e il conteggio dei vertici prima di scegliere.

Come si ricostruisce il percorso più breve effettivo?

Le distanze da sole non rivelano la sequenza dei vertici. Mantenere una matrice next[i][j] inizializzata su j quando esiste un arco diretto da i a j. Ogni volta che il percorso attraverso k migliora dist[i][j], imposta next[i][j] su next[i][k]. Per ricostruire un percorso spostarsi ripetutamente dal vertice corrente a next[current][destination] fino a raggiungere la destinazione.

Verifica la presenza di coppie irraggiungibili prima della ricostruzione e proteggiti dai casi di ciclo negativo. Se una coppia può viaggiare verso un ciclo negativo e poi raggiungere la destinazione, non esiste un percorso più breve finito da ricostruire.

In che modo Floyd-Warshall rileva i cicli negativi?

Al termine dell'algoritmo, ispeziona la diagonale. Un valore dist[v][v] < 0 dimostra che un ciclo di peso negativo è raggiungibile da v e può tornare a v. Questo è più forte che trovare semplicemente un fronte negativo; i bordi negativi possono esistere in grafici con percorsi minimi perfettamente validi.

Se l'intervistatore chiede quali coppie sono interessate, identificare ogni i e j per cui i può raggiungere un vertice v e v può raggiungere j. Queste coppie possono ripetere il ciclo negativo arbitrariamente molte volte, quindi il loro valore del percorso più breve non è finito.

Quando dovresti scegliere un altro algoritmo del percorso più breve?

Utilizzare la ricerca in ampiezza per grafici non ponderati, Dijkstra per problemi con una singola sorgente con pesi non negativi e Bellman–Ford per una singola sorgente quando sono importanti i pesi negativi o il rilevamento raggiungibile del ciclo negativo. Floyd–Warshall è la scelta diretta quando sono richieste distanze per tutte le coppie e il tempo cubico è accettabile.

Quali errori durante il colloquio dovresti evitare?

Non inserire k all'interno di un altro ciclo, dimenticare gli zeri sulla diagonale, aggiungere l'infinito senza guardia, confondere gli archi negativi con i cicli negativi o affermare che lo spazio della matrice O(V²) include automaticamente l'input in ogni rappresentazione. Chiarire se il grafico è diretto, se esistono bordi paralleli e se l'intervistatore ha bisogno di distanze, percorsi o coppie ciclabili.

Esercitati con il flusso di lavoro dell'assistente per il colloquio di codifica, confronta l'algoritmo Bellman-Ford ed esamina il cheat sheet sulla complessità della Big O.

Domande frequenti

Esercitati con l'invariante, non solo con i cicli

YesToTheOffer può aiutarti a strutturare una spiegazione della codifica, radicarla nelle tue note di preparazione private, esaminare casi limite e conservare la trascrizione dell'intervista per una revisione successiva.