Bellman Ford-Algorithmus: Leitfaden für Coding-Interviews

TL;DR: Der Bellman-Ford-Algorithmus findet kürzeste Single-Source-Pfade in einem gewichteten gerichteten Graphen, selbst wenn einige Kanten negative Gewichte haben. Initialisieren Sie den Quellabstand auf Null, alle anderen auf Unendlich, entspannen Sie jede Kante bis zu V minus 1 Mal und führen Sie dann einen zusätzlichen Durchgang durch: Jede weitere Verbesserung beweist, dass ein erreichbarer Zyklus mit negativem Gewicht existiert.

Was ist der Bellman-Ford-Algorithmus?

Bellman Ford ist ein Kurzwegalgorithmus im dynamischen Programmierstil. Nach dem ersten vollständigen Durchgang nutzen die bekanntesten Pfade höchstens eine Kante; nach der zweiten höchstens zwei Kanten. Ein einfacher Pfad enthält höchstens V minus 1 Kanten, was sowohl die Schleifenanzahl als auch das Korrektheitsargument erklärt. Im Gegensatz zum Dijkstra-Algorithmus geht Bellman Ford nicht von nichtnegativen Kantengewichten aus.

Wie erklärt man Kantenrelaxation?

Für eine Kante von u nach v mit dem Gewicht w fragt die Entspannung, ob Abstand[u] + w kleiner als Abstand[v] ist. Führen Sie die Addition nur durch, wenn Sie erreichbar sind. Wenn der Kandidat besser ist, aktualisieren Sie die Distanz[v] und setzen Sie den Vorgänger[v] auf u. Das Vorgänger-Array ist für Entfernungen optional, lässt Sie aber den tatsächlichen Weg rekonstruieren und Ihr Ergebnis anschaulich erklären.

Wie spürt man Bellman Ford in einem Interview auf?

Verwenden Sie ein kleines Diagramm und schreiben Sie pro Durchgang eine Distanzzeile. Beginnen Sie mit Quelle A bei 0 und jedem zweiten Scheitelpunkt im Unendlichen. Scannen Sie die vollständige Kantenliste in konsistenter Reihenfolge und zeichnen Sie jede Aktualisierung auf. Stoppen Sie frühzeitig, wenn ein ganzer Durchgang keine Änderungen bewirkt. Machen Sie deutlich, dass die Kantenreihenfolge Zwischenzeilen ändern kann, nicht jedoch die endgültigen korrekten Abstände, wenn kein erreichbarer negativer Zyklus vorhanden ist.

Welchen Pseudocode sollten Sie schreiben?

Erstellen Sie Abstands- und Vorgängerarrays und wiederholen Sie dann einen vollständigen Kantenscan V minus 1 Mal. Verwenden Sie für die vorzeitige Beendigung ein geändertes Flag. Scannen Sie abschließend noch einmal alle Kanten und melden Sie einen negativen Zyklus, wenn sich die erreichbare Distanz noch verbessern lässt. Wählen Sie im Produktionscode einen numerischen Typ aus, der Pfadsummen speichern und den Unendlichkeitswächter vor der Addition schützen kann.

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

Die standardmäßige Adjacency-Edge-List-Implementierung läuft in O(VE)-Zeit, da sie E Kanten bei jedem von V minus 1 Durchgängen plus einem Erkennungsdurchlauf scannen kann. Es verwendet O(V)-Hilfsraum für Entfernungen und Vorgänger. Frühzeitiges Stoppen verbessert günstige Eingaben, aber die Worst-Case-Grenze bleibt O(VE).

Wann sollten Sie Bellman Ford statt Dijkstra wählen?

Wählen Sie Bellman Ford, wenn negative Kantengewichte zulässig sind oder wenn der Interviewer ausdrücklich nach einer erreichbaren Erkennung negativer Zyklen fragt. Wählen Sie Dijkstra mit einer Prioritätswarteschlange für Diagramme, deren Kantengewichte alle nicht negativ sind, da dies normalerweise schneller ist. Für kürzeste Pfade aller Paare klären Sie zunächst die Diagrammdichte, negative Gewichte und ob Pfade oder nur Abstände erforderlich sind.

Welche Fehler sollten Sie vermeiden?

Entspannen Sie sich nicht von einem unerreichbaren Scheitelpunkt, verwechseln Sie eine negative Kante nicht mit einem negativen Zyklus und behaupten Sie nicht, dass jeder negative Zyklus das Ergebnis ungültig macht: Nur ein Zyklus, der von der Quelle aus erreichbar ist, wirkt sich auf seine kürzesten Pfade aus. Vermeiden Sie außerdem, nur V minus 2 Durchgänge auszuführen, den letzten Erkennungsdurchlauf zu überspringen oder einen Pfad ohne Beibehaltung der Vorgänger zu rekonstruieren.

Wie kann man die Erklärung üben?

Üben Sie drei Versionen: eine 30-sekündige Definition, eine zweiminütige Erklärung der Korrektheit und eine vollständige Implementierung. Testen Sie einen nicht erreichbaren Scheitelpunkt, eine negative Kante ohne Zyklus, einen erreichbaren negativen Zyklus und einen Graphen, der sich früh stabilisiert. Dies trennt den gespeicherten Code vom echten Verständnis.

Verwenden Sie KI, um bereits verstandenes Material zu organisieren, Erklärungen einzustudieren und Ihre Leistung zu überprüfen. Befolgen Sie die Regeln des Arbeitgebers und des Bewertungsanbieters und erfinden Sie niemals Erfahrungen, Zahlen oder Ergebnisse.

Fahren Sie mit dem Leitfaden für KI-Interview-Copiloten, lebenslaufbasierte Vorbereitung und Workflow für die Überprüfung nach dem Interview fort.

Häufig gestellte Fragen

Üben Sie mit Beweisen, nicht mit einem Skript

YesToTheOffer kann die Vorbereitung und Antwortstruktur in Echtzeit in Ihrem Lebenslauf, Ihrer Rollenbeschreibung und Ihren privaten Notizen verankern und dann ein Transkript für die Durchsicht nach dem Vorstellungsgespräch aufbewahren.