Floyd-Warshall-Algorithmus: Leitfaden für Coding-Interviews

TL;DR: Der Floyd-Warshall-Algorithmus berechnet die kürzesten Pfade aller Paare mit dynamischer Programmierung. Initialisieren Sie eine Distanzmatrix aus dem Diagramm und aktualisieren Sie dann für jeden Zwischenscheitelpunkt k jedes Paar mit dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Es läuft in O(V³) Zeit und O(V²) Raum und kann negative Zyklen durch negative diagonale Einträge aufdecken.

Was ist der Floyd-Warshall-Algorithmus?

Floyd-Warshall ist ein dynamischer Programmieralgorithmus für kürzeste Pfade zwischen jedem geordneten Eckpunktpaar. Es funktioniert mit gerichteten oder ungerichteten gewichteten Graphen und lässt negative Kanten zu. Wenn jedoch ein relevanter Zyklus mit negativem Gewicht vorhanden ist, haben einige kürzeste Pfade kein endliches Minimum, da das wiederholte Durchlaufen des Zyklus die Pfadkosten immer weiter senkt.

Der Algorithmus ist einprägsam, weil er ein globales Pfadproblem in eine einzige Entscheidung umwandelt: Ist für den aktuellen Zwischenscheitelpunkt k der beste bekannte Pfad von i nach j so wie er ist besser oder geht er von i nach k und dann von k nach j?

Wie leitet man die Wiederholung ab?

Definieren Sie D(k, i, j) als den kürzesten Abstand von i nach j, dessen Zwischenscheitelpunkte nur von den ersten k Scheitelpunkten stammen dürfen. Ein kürzester zulässiger Pfad vermeidet entweder den Scheitelpunkt k und behält D(k−1, i, j) bei oder verwendet k und teilt sich in den besten zulässigen Pfad von i nach k plus den besten zulässigen Pfad von k nach j auf.

Das ergibt die Wiederholung:

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

Da die Stufe k nur auf kompatible Weise von den Werten der Stufe k-1 abhängt, kann die Matrix direkt aktualisiert werden. Diese Argumentation erklärt auch die kritische Schleifenreihenfolge: k muss die äußerste Schleife sein. Das Platzieren von i oder j außerhalb ändert die Invariante und kann dazu führen, dass teilweise zulässige Pfade falsch verwendet werden.

Wie initialisiert man die Distanzmatrix?

Erstellen Sie eine V-mal-V-Matrix. Setzen Sie dist[i][i] auf Null, setzen Sie die Zelle einer direkten Kante auf ihr Gewicht und verwenden Sie Unendlich, wenn keine direkte Kante vorhanden ist. Wenn parallele Kanten möglich sind, halten Sie das kleinste direkte Gewicht ein. Bevor Sie zwei Abstände hinzufügen, stellen Sie sicher, dass beide endlich sind, damit ein Unendlichkeitswächter nicht überläuft oder einen falschen Kandidaten erzeugt.

Wie verfolgt man Floyd-Warshall in einem Interview?

Beschriften Sie die Matrixzeilen als Quellen und die Spalten als Ziele. Zeigen Sie die Ausgangsmatrix an, wählen Sie dann ein k aus und werten Sie repräsentative Zellen aus. Vergleichen Sie für jede Zelle den aktuellen Wert mit der Route durch k. Aktualisieren Sie nur, wenn beide Segmente erreichbar sind und die neue Summe kleiner ist.

Normalerweise müssen Sie nicht jede Matrix für ein großes Beispiel zeichnen. Verfolgen Sie genügend Zellen, um die Invariante zu demonstrieren, einschließlich einer Verbesserung und eines unveränderten Werts. Geben Sie an, dass nach Abschluss von k jeder Matrixeintrag unter Pfaden, deren Zwischenscheitelpunkte auf die verarbeitete Menge beschränkt sind, optimal ist.

Welchen Pseudocode sollten Sie schreiben?

Verwenden Sie drei verschachtelte Schleifen mit k an der Außenseite:

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

Erklären Sie die endlichen Schecks und den numerischen Typ. In Sprachen mit einem großen ganzzahligen Sentinel kann das Hinzufügen von Unendlich zu einem negativen Wert endlich oder überlaufend aussehen. Ein Wächter ist Teil der Korrektheit, nicht nur ein Implementierungsdetail.

Was sind die zeitlichen und räumlichen Komplexitäten?

Die drei Schleifen untersuchen jede Kombination von k, i und j, sodass die Laufzeit O(V³) beträgt. Die Distanzmatrix belegt O(V²) Platz. Durch die direkte Aktualisierung wird eine dreidimensionale Tabelle vermieden, während eine Next-Hop- oder Vorgängermatrix für die Pfadrekonstruktion O(V²) mehr Platz hinzufügt.

Floyd-Warshall ist oft für Graphen mit geringer Dichte attraktiv, da seine Implementierung kompakt und vorhersehbar ist. Für einen großen, dünn besetzten Graphen mit nichtnegativen Kanten kann die Ausführung von Dijkstra aus jeder Quelle effizienter sein. Vergleichen Sie immer die erforderliche Ausgabe, die Diagrammdichte, die Gewichtsbeschränkungen und die Scheitelpunktanzahl, bevor Sie eine Auswahl treffen.

Wie rekonstruiert man den tatsächlich kürzesten Weg?

Entfernungen allein geben keinen Aufschluss über die Scheitelpunktsequenz. Behalten Sie eine auf j initialisierte next[i][j]-Matrix bei, wenn eine direkte Kante von i nach j existiert. Wenn das Routing durch k dist[i][j] verbessert, setzen Sie next[i][j] auf next[i][k]. Um einen Pfad zu rekonstruieren, bewegen Sie sich wiederholt vom aktuellen Scheitelpunkt zu next[current][destination], bis Sie das Ziel erreichen.

Überprüfen Sie vor der Rekonstruktion, ob nicht erreichbare Paare vorhanden sind, und schützen Sie sich vor Fällen negativer Zyklen. Wenn ein Paar zu einem negativen Zyklus reisen und dann das Ziel erreichen kann, gibt es keinen endlichen kürzesten Weg zur Rekonstruktion.

Wie erkennt Floyd-Warshall negative Zyklen?

Überprüfen Sie nach Abschluss des Algorithmus die Diagonale. Ein Wert dist[v][v] < 0 beweist, dass ein Zyklus mit negativem Gewicht von v aus erreichbar ist und zu v zurückkehren kann. Dies ist stärker als nur das Finden einer negativen Kante; Negative Kanten können in Diagrammen mit vollkommen gültigen kürzesten Pfaden existieren.

Wenn der Interviewer fragt, welche Paare betroffen sind, identifizieren Sie alle i und j, für die i einen solchen Scheitelpunkt v und v j erreichen kann. Diese Paare können den negativen Zyklus beliebig oft durchlaufen, sodass ihr Wert für den kürzesten Weg nicht endlich ist.

Wann sollten Sie einen anderen Kürzeste-Weg-Algorithmus wählen?

Verwenden Sie die Breitensuche für ungewichtete Diagramme, Dijkstra für Einzelquellenprobleme mit nichtnegativen Gewichten und Bellman-Ford für eine Einzelquelle, wenn negative Gewichte oder die Erkennung erreichbarer negativer Zyklen von Bedeutung sind. Floyd-Warshall ist die direkte Wahl, wenn Abstände aller Paare erforderlich sind und die Kubikzeit akzeptabel ist.

Welche Fehler im Vorstellungsgespräch sollten Sie vermeiden?

Setzen Sie k nicht in eine andere Schleife, vergessen Sie Nullen auf der Diagonale, fügen Sie Unendlich ohne Schutz hinzu, verwechseln Sie negative Kanten nicht mit negativen Zyklen und behaupten Sie nicht, dass der Matrixraum O(V²) die Eingabe automatisch in jede Darstellung einbezieht. Klären Sie, ob der Graph gerichtet ist, ob parallele Kanten vorhanden sind und ob der Interviewer Abstände, Pfade oder vom Zyklus betroffene Paare benötigt.

Üben Sie den Workflow des Coding-Interview-Assistenten, vergleichen Sie den Bellman-Ford-Algorithmus und sehen Sie sich den Big O-Komplexitäts-Spickzettel an.

Häufig gestellte Fragen

Üben Sie die Invariante, nicht nur die Schleifen

YesToTheOffer kann dabei helfen, eine Codierungserklärung zu strukturieren, sie in Ihren privaten Vorbereitungsnotizen zu verankern, Randfälle zu untersuchen und das Interviewprotokoll für eine spätere Durchsicht aufzubewahren.