Floyd-Warshall-algoritme: interviewgids voor codering

TL; DR: Het Floyd-Warshall-algoritme berekent de kortste paden van alle paren met dynamische programmering. Initialiseer een afstandsmatrix uit de grafiek en update vervolgens voor elk tussenliggend hoekpunt k elk paar met dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Het loopt in O(V³) tijd en O(V²) ruimte en kan negatieve cycli blootleggen via negatieve diagonale ingangen.

Wat is het Floyd-Warshall-algoritme?

Floyd-Warshall is een dynamisch programmeeralgoritme voor de kortste paden tussen elk geordend paar hoekpunten. Het werkt met gerichte of ongerichte gewogen grafieken en maakt negatieve randen mogelijk. Als er echter een relevante cyclus met een negatief gewicht bestaat, hebben sommige kortste paden geen eindig minimum, omdat het herhaaldelijk doorlopen van de cyclus de padkosten blijft verlagen.

Het algoritme is gedenkwaardig omdat het een globaal padprobleem omzet in één beslissing: is voor het huidige tussenliggende hoekpunt k het bekendste pad van i naar j beter zoals het is, of gaat het van i naar k en vervolgens van k naar j?

Hoe herleid je de herhaling?

Definieer D(k, i, j) als de kortste afstand van i tot j waarvan de tussenliggende hoekpunten alleen uit de eerste k hoekpunten mogen komen. Een kortst toegestane pad vermijdt ofwel hoekpunt k, waarbij D(k−1, i, j) behouden blijft, of gebruikt k en splitst zich op in het best toegestane pad van i naar k plus het best toegestane pad van k naar j.

Dat geeft de herhaling:

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

Omdat fase k alleen op een compatibele manier afhankelijk is van fase k−1-waarden, kan de matrix ter plaatse worden bijgewerkt. Deze redenering verklaart ook de kritische lusvolgorde: k moet de buitenste lus zijn. Als u i of j buiten plaatst, verandert de invariant en kunnen gedeeltelijk toegestane paden verkeerd worden gebruikt.

Hoe initialiseer je de afstandsmatrix?

Maak een V bij V-matrix. Stel dist[i][i] in op nul, stel de cel van een directe rand in op het gewicht ervan en gebruik oneindig als er geen directe rand bestaat. Als evenwijdige randen mogelijk zijn, houd dan het kleinste directe gewicht aan. Voordat u twee afstanden optelt, controleert u of beide eindig zijn, zodat een oneindige schildwacht niet overstroomt of een valse kandidaat creëert.

Hoe traceer je Floyd-Warshall in een interview?

Label de matrixrijen als bronnen en kolommen als bestemmingen. Toon de initiële matrix, kies vervolgens één k en evalueer representatieve cellen. Vergelijk voor elke cel de huidige waarde met de route door k. Alleen bijwerken als beide segmenten bereikbaar zijn en de nieuwe som kleiner is.

Voor een groot voorbeeld hoeft u normaal gesproken niet elke matrix te tekenen. Traceer voldoende cellen om de invariant aan te tonen, inclusief één verbetering en één ongewijzigde waarde. Stel dat na het voltooien van k elke matrixinvoer optimaal is tussen paden waarvan de tussenliggende hoekpunten beperkt zijn tot de verwerkte set.

Welke pseudocode moet je schrijven?

Gebruik drie geneste lussen met k aan de buitenkant:

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])

Leg de eindige controles en het numerieke type uit. In talen met een groot geheel getal kan het toevoegen van oneindigheid aan een negatieve waarde er eindig uitzien of overlopen. Een bewaker maakt deel uit van correctheid, niet slechts een implementatiedetail.

Wat zijn de complexiteiten in tijd en ruimte?

De drie lussen onderzoeken elke combinatie van k, i en j, dus de looptijd is O(V³). De afstandsmatrix neemt O(V²) ruimte in beslag. Bij lokaal bijwerken wordt een driedimensionale tabel vermeden, terwijl een volgende hop- of voorgangermatrix voor padreconstructie O(V²) meer ruimte toevoegt.

Floyd-Warshall is vaak aantrekkelijk voor grafieken met een bescheiden dichtheid, omdat de implementatie ervan compact en voorspelbaar is. Voor een grote schaarse grafiek met niet-negatieve randen kan het efficiënter zijn om Dijkstra vanuit elke bron te laten lopen. Vergelijk altijd de vereiste uitvoer, grafiekdichtheid, gewichtsbeperkingen en aantal hoekpunten voordat u een keuze maakt.

Hoe reconstrueer je het daadwerkelijke kortste pad?

Afstanden alleen onthullen niet de hoekpuntreeks. Handhaaf een next[i][j]-matrix geïnitialiseerd op j wanneer er een directe rand van i naar j bestaat. Telkens wanneer routeren door k dist[i][j] verbetert, stelt u next[i][j] in op next[i][k]. Om een ​​pad te reconstrueren, beweegt u herhaaldelijk van het huidige hoekpunt naar next[current][destination] totdat u de bestemming bereikt.

Controleer vóór de reconstructie op onbereikbare paren en bescherm tegen gevallen met een negatieve cyclus. Als een paar naar een negatieve cyclus kan reizen en vervolgens de bestemming kan bereiken, is er geen eindig kortste pad om te reconstrueren.

Hoe detecteert Floyd-Warshall negatieve cycli?

Nadat het algoritme is voltooid, inspecteert u de diagonaal. Een waarde dist[v][v] < 0 bewijst dat een cyclus met een negatief gewicht bereikbaar is vanaf v en kan terugkeren naar v. Dit is sterker dan alleen het vinden van een negatieve voorsprong; negatieve randen kunnen voorkomen in grafieken met perfect geldige kortste paden.

Als de interviewer vraagt ​​welke paren betrokken zijn, identificeer dan elke i en j waarvoor ik zo'n hoekpunt v kan bereiken en v kan j bereiken. Deze paren kunnen de negatieve cyclus willekeurig vele keren doorlopen, dus hun kortste padwaarde is niet eindig.

Wanneer moet je een ander kortste-pad-algoritme kiezen?

Gebruik breedte-eerst zoeken voor ongewogen grafieken, Dijkstra voor problemen met één bron met niet-negatieve gewichten, en Bellman-Ford voor een enkele bron wanneer negatieve gewichten of bereikbare detectie van negatieve cyclussen van belang zijn. Floyd-Warshall is de directe keuze wanneer afstanden van alle paren vereist zijn en de kubieke tijd acceptabel is.

Welke interviewfouten moet je vermijden?

Plaats k niet in een andere lus, vergeet nullen op de diagonaal, voeg oneindigheid toe zonder beveiliging, verwar negatieve randen niet met negatieve cycli, of claim dat de matrixruimte O(V²) de invoer automatisch in elke representatie omvat. Maak duidelijk of de grafiek gericht is, of er parallelle randen bestaan ​​en of de interviewer afstanden, paden of door de cyclus beïnvloede paren nodig heeft.

Oefen de workflow van de codeerinterviewassistent, vergelijk het Bellman-Ford-algoritme en bekijk het Big O complexiteitspiekbriefje.

Veelgestelde vragen

Oefen de invariant, niet alleen de lussen

YesToTheOffer kan helpen bij het structureren van een codeeruitleg, het onderbouwen ervan in uw persoonlijke voorbereidingsnotities, het onderzoeken van randgevallen en het bewaren van het transcript van het interview voor latere beoordeling.