Floyd-Warshall: Korteste veje mellem alle par

Floyd-Warshall beregner korteste stier mellem alle par af noder i en vægtet graf — inklusive grafer med negative kantvægte (men ikke negative cyklusser). At køre Dijkstra fra hver kilde tager O(V × (V+E) log V); Floyd-Warshall kører i O(V³)

Floyd-Warshalls indsigt: dp[i][j][k] = den korteste sti fra i til j, hvor kun noderne {0, 1, ..., k} bruges som mellemled. Enten bruger den korteste sti node k som mellemled, eller også gør den ikke. Hvis den gør: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Hvis ikke: dp[i][j][k] = dp[i][j][k-1]. Da den tredje dimension kun bevæger sig fremad, kan den elimineres — vi opdaterer direkte.

Start med en V×V-matrice: dist[i][i] = 0 (afstand fra en node til sig selv er nul), dist[i][j] = weight for direkte kanter og dist[i][j] = inf for par uden kanter. Gennemløb derefter alle mellemliggende noder k, og opdatér parrene (i, j). Den ydre løkke over k skal komme først, så vi korrekt opbygger stier gennem et stadigt større sæt af tilladte mellemled.

Lad os gennemgå Floyd-Warshall på en graf med 4 noder. Efter behandling af hver mellemliggende node k udfyldes matricen med kortere stier, der går gennem node k. Algoritmen håndterer naturligt flere kanter ved gradvist at opbygge de korteste stier.

Efter Floyd-Warshall er kørt, skal du kontrollere hoveddiagonalen: Hvis en dist[i][i] < 0, findes der en negativ cyklus, der går gennem node i. Det skyldes, at en negativ cyklus gør det muligt at nå i fra i med negativ omkostning. Hvis der ikke findes en negativ cyklus, forbliver alle diagonale elementer 0.

For at genskabe den faktiske sti fra i til j skal du vedligeholde en next[i][j]-matrix: Oprindeligt er next[i][j] = j for direkte kanter. Ved en opdatering via den mellemliggende node k skal du sætte next[i][j] = next[i][k]. For at genskabe stien skal du starte ved i og følge next-pegerne, indtil du når j. Det tilføjer O(V²) plads og O(V) pr. stigenskabelse.

En enklere variant: transitiv lukning besvarer spørgsmålet 'kan node j nås fra node i?' for alle par. Erstat afstande med booleske værdier: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Dette er Floyd-Warshall med boolesk OR i stedet for addition og min. Initialisér reach[i][i] = True og reach[i][j] = True for direkte kanter.

Floyd-Warshall: O(V³)-tid, O(V²)-plads. For tætte grafer (E ≈ V²) med V ≤ 300 er dette hurtigere end at køre Dijkstra V gange (også O(V³) i det tilfælde). For sparsomme grafer med V = 1000 og E = 3000 koster V Dijkstra-kørsler O(V×E×log V) ≈ 33M, mens Floyd-Warshall koster O(V³) = 10⁹ — Dijkstra vinder. Du skal vide, hvornår hver algoritme er passende.

Sæt alle kantvægte til 1 (eller brug en boolesk nabomatrix med Floyd-Warshall, hvor du bruger addition i stedet for min): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Dette beregner det mindste antal hop mellem alle par — det samme resultat som BFS mellem alle par, men beregnet med ét O(V³)-gennemløb med Floyd-Warshall.

Floyd-Warshall dukker op i interviews om opgaver, der handler om: (1) afstande mellem alle par i en lille graf, (2) at finde ud af, om der findes en cyklus med negativ samlet vægt, (3) at beregne korteste veje i problemer med begrænsningsudbredelse og (4) opgaver, der udtrykkeligt beder om løsninger i O(V³), hvor V ≤ 200. Nævn altid strukturen med tre løkker og kravet om, at der ikke må være negative cyklusser, for at algoritmen er korrekt.

For urettede grafer skal du tilføje begge retninger for hver kant: dist[u][v] = dist[v][u] = weight. Resten af algoritmen er identisk. Den resulterende matrix er symmetrisk: dist[i][j] == dist[j][i] for alle par. Vær forsigtig under initialiseringen, så du ikke ved en fejl tildeler retningsbestemte kanter — urettede kanter skal tilføjes i begge retninger til den indledende matrix, før de tre løkker køres.

I denne lektion har du lært: Floyd-Warshall beregner de korteste veje mellem alle par med tre indlejrede løkker og rekurrensen dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), negative cyklusser kan registreres ved at kontrollere, om en dist[i][i] < 0 efter afslutningen, og algoritmen kører i O(V³)-tid og bruger O(V²)-plads. Næste gang genbesøger vi anvendelser af korteste veje med Network Delay Time og teknikker til rekonstruktion af veje.