Dijkstra-Interviewfragen

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was eine Dijkstra-Frage wirklich prüft

Niemand soll den Dijkstra-Algorithmus aufsagen. Was Sie bekommen, ist ein Problem, dessen Gewichte keine Entfernungen sind, und das Interview fragt, ob Sie erkennen, dass die Form des Algorithmus trotzdem passt.

Diese Form ist: eine Prioritätswarteschlange, geordnet nach einem Kostenlabel, eine Relaxierungsregel, die das Label eines Nachbarn verbessert, und die Garantie, dass das Label eines Knotens nach dem Entnehmen endgültig ist. Ändern Sie, was „Kosten“ bedeutet, ändern Sie den Vergleich, und dieselben zwölf Zeilen lösen minimalen Aufwand, maximale Wahrscheinlichkeit, billigste Flüge und ein halbes Dutzend weiterer Fragen. Das Interview prüft, ob Sie wissen, welche Teile Sie ändern dürfen und welcher nicht. Dijkstras ursprüngliche Notiz von 1959 ist zwei Seiten lang, und die Idee musste seitdem nicht überarbeitet werden.

Die acht folgenden Probleme sind die, die immer wiederkehren, jeweils mit Lösung, Nachfrage und dem Fehler, der das Angebot kostet. Jedes Rechenbeispiel wurde per Skript ausgeführt.

2. Die Vorlage und Lazy Deletion

Schreiben Sie das ohne Nachdenken. Die Kommentare markieren die zwei Zeilen, die eine korrekte Implementierung von einer plausiblen unterscheiden.

import heapq

def dijkstra(adj, src, n):          # adj[u] = [(v, w), ...] mit w >= 0
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:             # VERALTETER Eintrag: ein besseres Label wurde
            continue                # nach dessen Einfügen gefunden. Überspringen.
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))   # einfügen, nie decrease-key
    return dist

Die Zeile if d > dist[u]: continue ist die ganze Antwort auf „wie gehen Sie mit decrease-key um“. Ein binärer Heap hat kein effizientes decrease-key. Statt einen Eintrag zu aktualisieren, fügen Sie also einen zweiten ein und ignorieren die veraltete Entnahme. Das ist Lazy Deletion, und sie benennen zu können, ist mehr wert als der Code darum herum. Der Heap kann daher bis zu O(E) Einträge statt O(V) enthalten, weshalb die Schranke O((V + E) log V) lautet und nicht O((V + E) log E): Die Logarithmen unterscheiden sich nur um einen konstanten Faktor, da E < V2.

Zwei weitere Dinge sollten Sie laut sagen. Ein Knoten ist abgeschlossen, sobald er mit einem aktuellen Label entnommen wird, und sein Abstand ändert sich danach nie mehr; auf dieser Invariante beruht die gierige Wahl. Und Sie brauchen keine eigene visited-Menge, denn die Veraltungsprüfung weist jede zweite Entnahme bereits zurück.

3. Network Delay Time und die Rekonstruktion des Weges

Die Frage. Gegeben ein gerichteter gewichteter Graph und eine Quelle: Wie lange dauert es, bis jeder Knoten erreicht ist? Geben Sie -1 zurück, wenn ein Knoten nie erreicht wird. Im Interview geht es um Signalausbreitung, Paketzustellung oder „wann erfährt der letzte Server davon“.

Das ist einfacher Dijkstra plus eine Zeile: Die Antwort ist max(dist), und -1, wenn noch ein Eintrag unendlich ist.

Auf dem laufenden Graphen schließt Dijkstra ab 0 die Knoten in der Reihenfolge 0, 2, 1, 3, 4, 5 ab und liefert die Abstände 0, 3, 1, 8, 10, 12. Achten Sie auf Knoten 1: Der Bogen 0 → 1 beschriftet ihn mit 4, dann verbessert 0 → 2 → 1 ihn auf 3, bevor er je entnommen wird. Genau so soll der Algorithmus arbeiten, und deshalb dürfen Sie sich beim Einfügen nie auf ein Label festlegen.

Die Nachfrage: Geben Sie den Weg zurück, nicht nur die Länge. Führen Sie ein parent-Array, setzen Sie parent[v] = u im selben Zweig, der dist[v] verbessert, laufen Sie es dann vom Ziel rückwärts ab und kehren Sie die Liste um. Auf diesem Graphen ergibt das 0 → 2 → 1 → 4 → 5, Kosten 12. Sagen Sie „ein kürzester Weg“ statt „der“: Hier gibt es zwei mit Kosten 12, wie Abschnitt 7 zeigt.

Die Falle. Das Setzen von parent[v] außerhalb des Verbesserungszweigs, sodass der letzte Knoten gespeichert wird, der es versucht hat, statt des erfolgreichen. Die Abstände bleiben richtig und der rekonstruierte Weg ist falsch, und das ist die schlimmste Art von Fehler, die man im Review finden muss.

4. Billigste Flüge mit höchstens K Stopps

Die Frage. Die billigste Route von der Quelle zum Ziel mit höchstens K Zwischenstopps.

An dieser Frage scheitern viele, denn einfacher Dijkstra ist hier falsch. Seine Korrektheit beruht darauf, dass ein Knoten ein endgültiges Label hat, doch unter einer Stopp-Grenze hat ein Knoten für jede Anzahl genutzter Stopps andere beste Kosten, und eine billige Route, die zu viele Sprünge verbraucht, kann schlechter sein als eine teure kurze. Einen Knoten einmal abzuschließen, verwirft genau die Alternative, die Sie brauchen.

Zwei korrekte Antworten, und beide zu kennen, ist der Punkt.

Den Zustand erweitern. Behalten Sie Dijkstra bei, aber machen Sie den Knoten zu einem Paar (node, stops_used). Das Label ist jetzt pro Paar endgültig, also gilt die Invariante wieder.

def cheapest(adj, src, dst, K, n):
    best = [[float('inf')] * (K + 2) for _ in range(n)]
    best[src][0] = 0
    heap = [(0, src, 0)]                     # (Kosten, Knoten, Stopps)
    while heap:
        c, u, k = heapq.heappop(heap)
        if u == dst: return c                # erste Entnahme von dst ist optimal
        if k > K or c > best[u][k]: continue
        for v, w in adj[u]:
            if c + w < best[v][k + 1]:
                best[v][k + 1] = c + w
                heapq.heappush(heap, (c + w, v, k + 1))
    return -1

Oder Bellman-Ford verwenden, die sauberere Antwort. Jede Kante genau K + 1 Mal zu relaxieren, jede Runde ausgehend von einer Momentaufnahme der vorigen Runde, liefert direkt die billigste Route mit höchstens K + 1 Kanten. Das ist Bellmans Formulierung von 1958, und sie läuft in O(K × E) ganz ohne Heap. Sie ungefragt anzubieten, macht einen sehr guten Eindruck.

Die Falle. Die Bellman-Ford-Version muss von einer Kopie der Abstände der vorigen Runde aus relaxieren. In-place-Relaxierung lässt eine einzelne Runde über mehrere Kanten weiterlaufen, was stillschweigend mehr als K Stopps erlaubt und eine zu billige, plausibel aussehende Antwort liefert.

5. Weg mit minimalem Aufwand: das Plus ersetzen

Die Frage. Minimieren Sie die größte einzelne Kante auf der Route statt der Summe. Formulierungen: Weg mit minimalem Aufwand, Schwimmen bei steigendem Wasser, das maximale Gewicht, das Sie tragen können müssen.

Die Einsicht ist, dass Dijkstra nie wirklich Addition brauchte. Er braucht nur, dass das Verlängern eines Weges seine Kosten nicht verbessern kann, damit ein abgeschlossenes Label endgültig bleibt. max erfüllt das genauso gut wie +, also ändern Sie eine Zeile:

        cand = max(d, w)          # statt d + w
        if cand < best[v]:
            best[v] = cand
            heapq.heappush(heap, (cand, v))

Auf dem laufenden Graphen sind die Minimax-Werte ab Knoten 0 0, 2, 1, 5, 5, 5, also ist der beste Engpass zu Knoten 5 5: Das Durchprobieren jeder Route bestätigt es. Dass es ein wirklich anderes Ziel ist, sieht man an den zwei billigsten Routen, die beide 12 kosten, aber größte Bögen von 5 und 7 haben. Die Summe zu minimieren und den größten Bogen zu minimieren, ist nicht dieselbe Frage, und im Allgemeinen muss die engpassoptimale Route überhaupt keine kürzeste sein.

Die Nachfrage: Was kann das Plus sonst noch ersetzen? Jede monotone Operation, also eine, bei der das Verlängern eines Weges seine Kosten nie senkt. max funktioniert, die Multiplikation von Wahrscheinlichkeiten in [0,1] funktioniert, wenn Sie maximieren, und die gewöhnliche Addition nichtnegativer Gewichte funktioniert. Subtraktion nicht, und das ist derselbe Grund, aus dem negative Kanten verboten sind.

Die Falle. Bei einer Gitterversion wird auch eine Lösung mit Union-Find oder binärer Suche plus BFS akzeptiert und ist manchmal schneller. Wenn Sie Dijkstra anbieten, sollten Sie begründen können, warum: kein Parameter, über den binär gesucht werden muss, und ein einziger Durchlauf.

6. Weg maximaler Wahrscheinlichkeit

Die Frage. Jede Kante hat eine Erfolgswahrscheinlichkeit; finden Sie die Route von der Quelle zum Ziel mit der höchsten Wahrscheinlichkeit, dass jede Kante gelingt.

Kosten werden multipliziert statt addiert, und Sie wollen das größte Produkt, also drehen Sie die Warteschlange zu einem Max-Heap um und relaxieren mit ×. Wahrscheinlichkeiten liegen in [0,1], also kann das Verlängern eines Weges das Produkt nur verkleinern, und das ist genau die Monotonie, die Dijkstra braucht.

        cand = p * pw                     # statt d + w
        if cand > best[v]:                # >, weil wir maximieren
            best[v] = cand
            heapq.heappush(heap, (-cand, v))   # negieren: heapq ist ein MIN-Heap

Auf einem Graphen mit einem direkten Bogen 0,30 von 0 nach 3 und der Route mit zwei Bögen 0 → 1 → 3 mit 0,9 und 0,8 ist die beste Wahrscheinlichkeit 0.72 über die Route mit zwei Bögen, die den einzelnen Bogen schlägt. Das ist der Satz, den Sie sagen sollten: Mehr Kanten können hier besser sein, was für gewöhnliche kürzeste Wege mit positiven Gewichten nie gilt.

Die Nachfrage: Warum nicht Logarithmen nehmen? Das können Sie, und es ist eine gute Antwort. Da log(ab) = log a + log b gilt, ist das Maximieren eines Produkts von Wahrscheinlichkeiten das Minimieren einer Summe von -log p, und diese Werte sind nichtnegativ, also greift unveränderter Dijkstra. Nennen Sie den Vorbehalt: Der log einer Wahrscheinlichkeit nahe null verliert in Gleitkommaarithmetik an Genauigkeit, und eine Kante mit Wahrscheinlichkeit 0 ergibt Unendlich, das Sie gesondert behandeln müssen.

7. Kürzeste Wege zählen

Die Frage. Wie viele verschiedene kürzeste Routen gibt es von der Quelle zum Ziel? Meist modulo 10⁹+7 gefragt.

Ein zusätzliches Array und ein zusätzlicher Zweig. Führen Sie neben dist auch ways mit, die Anzahl der kürzesten Routen zu jedem Knoten. Wenn eine Relaxierung ein Label verbessert, wird der Zähler ersetzt. Wenn sie gleichzieht, wird der Zähler addiert.

        if d + w < dist[v]:
            dist[v] = d + w
            ways[v] = ways[u]              # echt besser: ersetzen
            heapq.heappush(heap, (dist[v], v))
        elif d + w == dist[v]:
            ways[v] = (ways[v] + ways[u]) % MOD   # Gleichstand: ADDIEREN

Auf dem laufenden Graphen sind die Zähler 1, 1, 1, 1, 2, 2. Brute Force bestätigt: Von den 9 Routen von 0 nach 5 kosten zwei 12, nämlich 0→2→1→3→4→5 und 0→2→1→4→5. Beachten Sie, dass die Route mit weniger Kanten nicht allein die beste ist, und genau auf solche Details lohnt es sich hinzuweisen.

Die Nachfrage: Ist der Gleichstandszweig sicher? Ja, aber nur, weil ways[u] endgültig ist, wenn u entnommen wird, und jede Relaxierung von einem entnommenen Knoten ausgeht. Zähler von einem noch nicht abgeschlossenen Knoten zu addieren, würde doppelt zählen. Das ist das klarste Beispiel dafür, warum „abgeschlossen heißt endgültig“ die Invariante ist, auf die es ankommt, und nicht der Code.

Die Falle. Zu vergessen, dass das elif auf der Gleichheit sitzen muss und nicht im Verbesserungszweig. Als einzelnes if d + w <= dist[v] geschrieben, werden die Zähler bei Gleichstand ersetzt statt addiert, und die Antwort ist für jeden Knoten 1.

8. Der zweitkürzeste Weg

Die Frage. Finden Sie die zweitkürzeste Route von der Quelle zum Ziel. Klären Sie sofort, ob „zweite“ echt länger als die beste bedeutet oder einfach die nächste Route in einer Liste, in der Gleichstände getrennt zählen. Die beiden Antworten unterscheiden sich, und Interviewer fragen das mit Absicht.

Die Technik besteht darin, die Regel „nur einmal abschließen“ zu lockern: Behalten Sie die zwei besten Labels pro Knoten und lassen Sie einen Knoten zweimal entnehmen.

best1 = [inf] * n; best2 = [inf] * n
best1[src] = 0
heap = [(0, src)]
while heap:
    d, u = heapq.heappop(heap)
    if d > best2[u]: continue          # schlechter als beide gespeicherten Labels
    for v, w in adj[u]:
        nd = d + w
        if nd < best1[v]:
            best1[v], nd = nd, best1[v]     # altes Bestes zum Kandidaten herabstufen
            heapq.heappush(heap, (best1[v], v))   # das NEUE Beste muss sich auch ausbreiten
        if best1[v] < nd < best2[v]:        # echt schlechter als das Beste
            best2[v] = nd
            heapq.heappush(heap, (nd, v))

Auf dem laufenden Graphen sind die verschiedenen Routenkosten von 0 nach 5 12, 13, 14, 15, also ist die echt zweitbeste 13. Zählen Gleichstände dagegen getrennt, ist die Antwort wieder 12, weil zwei verschiedene Routen sie erreichen. Fragen Sie, bevor Sie programmieren.

Die Nachfrage: Verallgemeinern Sie auf K. Führen Sie eine Liste der K besten Labels pro Knoten oder verwenden Sie Yens Algorithmus für die K kürzesten schleifenfreien Wege, ein wirklich anderes und viel schwereres Problem. „Schleifenfrei ändert alles“ zu sagen, ist der richtige Instinkt: Ohne diese Einschränkung kann ein kürzester Kantenzug einen Zyklus mit Gewicht null endlos wiederholen.

9. Warum nichtnegative Gewichte nicht verhandelbar sind

Das fragt jeder Interviewer, und die meisten Kandidaten antworten „weil Dijkstra gierig ist“, was stimmt und nichts erklärt. Der genaue Grund: Der Algorithmus nimmt an, dass keine noch im Aufbau befindliche Route einen Knoten billiger erreichen kann, wenn dieser mit dem kleinsten Label der Warteschlange entnommen wird. Eine negative Kante bricht das, weil das Verlängern eines Weges seine Kosten senken kann.

Halten Sie ein konkretes Gegenbeispiel bereit. Nehmen Sie vier Knoten mit den Bögen 0→1 (1), 0→2 (2), 2→1 (−2) und 1→3 (1).

Dijkstra liefert 0, 0, 2, 2; die korrekte Antwort ist 0, 0, 2, 1. Die Feinheit lohnt es, genau benannt zu werden, denn sie ist interessanter als die übliche Antwort: Das Label von Knoten 1 ist am Ende korrekt. Er wird expandiert, solange sein Label noch 1 ist, und die spätere Verbesserung auf 0 wird durchaus geschrieben. Aber danach relaxiert niemand 1 → 3 erneut, also behält Knoten 3 den Wert 2 statt 1. Wer sagt „der falsche Wert taucht hinter der negativen Kante auf, nicht an ihr“, spricht erkennbar aus eigener Erfahrung.

Die Nachfrage: Was verwenden Sie stattdessen? Bellman-Ford, das jede Kante V - 1 Mal relaxiert, in O(VE), und negative Zyklen im V-ten Durchlauf erkennt. Wenn Sie alle Paare brauchen und negative Kanten, aber keinen negativen Zyklus haben, gewichtet Johnsons Algorithmus mit einem Bellman-Ford-Lauf so um, dass jedes Gewicht nichtnegativ wird, und führt dann Dijkstra von jedem Knoten aus. Cormen, Leiserson, Rivest und Stein liefern den vollständigen Korrektheitsbeweis für die gierige Wahl.

Die Falle. „Addieren Sie einfach eine Konstante zu jedem Gewicht, damit alle positiv sind.“ Das funktioniert nicht, und in einem Satz sagen zu können, warum, ist ein starkes Signal: Wer c zu jeder Kante addiert, addiert c × (number of edges) zu einer Route, was Routen mit mehr Kanten bestraft und damit ändert, welche Route die kürzeste ist.

10. Die Komplexitätsantworten

Halten Sie Schranke und Begründung bereit und nennen Sie die Datenstruktur. Zu sagen „Dijkstra ist O(E log V)“, ohne den Heap zu nennen, lädt zu einer Nachfrage ein, an der Sie dann scheitern.

Die heapbasierte Schranke ist Johnsons Ergebnis von 1977; die Verbesserung durch Fibonacci-Heaps stammt von Fredman und Tarjan, 1987. Der binäre Heap selbst ist Williams' Konstruktion von 1964. Die Fibonacci-Variante ist theoretisch besser und in der Praxis fast immer langsamer, weil ihre Konstanten groß sind, und das zu sagen, zeigt Urteilsvermögen statt Auswendiglernen. Sedgewick und Wayne liefern die kürzeste klare Darstellung der Alternative mit indizierter Prioritätswarteschlange, die decrease-key unterstützt.

Zwei Zahlen, die man haben sollte. Auf einem dünnen Graphen mit V = 105 und E = 5 × 105 ergibt die Schranke des binären Heaps etwa 10 Millionen Operationen gegenüber rund 2,2 Millionen beim Fibonacci-Heap: ein echter Abstand auf dem Papier, den die Konstanten in der Praxis tilgen. Und auf einem dichten Graphen, bei dem E gegen V2 geht, schlägt das einfache Array mit O(V2) den binären Heap mit O(V2 log V), und das ist der eine Fall, in dem die „naive“ Implementierung die richtige Wahl ist.

11. Fehler, an denen das Interview scheitert

Sortiert nach Häufigkeit; die ersten drei erklären die meisten abgelehnten Lösungen.

• Die Prüfung auf veraltete Einträge weglassen. Ohne if d > dist[u]: continue expandieren Sie Knoten von überholten Labels aus erneut. Die Antwort stimmt meist trotzdem, und die Laufzeit verschlechtert sich stark, weshalb der Fehler Tests übersteht.
• Dijkstra verwenden, wenn der Zustand nicht nur der Knoten ist. Eine Stopp-Grenze, ein Treibstoffbudget oder eine Klausel „höchstens K Rabatte“ bedeuten, dass das Label pro (vertex, resource)-Paar gilt. Nur den Knoten abzuschließen, verwirft die Route, die Sie brauchten.
• Bei negativen Gewichten zu Dijkstra greifen. Verwenden Sie Bellman-Ford und versuchen Sie nie, die Gewichte ins Positive zu verschieben.
• Vergessen, dass heapq ein Min-Heap ist. Etwas zu maximieren bedeutet, den negierten Schlüssel einzufügen, und die zweite Negation beim Herausnehmen zu vergessen, ist der klassische stille Fehler.
• Tupel vergleichen, die ein nicht ordnungsfähiges zweites Element enthalten. heappush(heap, (dist, node_object)) wirft einen Fehler, sobald zwei Abstände gleich sind und Python dazu übergeht, die Objekte zu vergleichen. Fügen Sie einen Index ein oder ergänzen Sie einen Zähler zur Auflösung von Gleichständen.
• Den Elternzeiger außerhalb des Verbesserungszweigs setzen. Die Abstände bleiben korrekt und der rekonstruierte Weg ist falsch.
• Zähler bei Gleichstand ersetzen statt addieren. Ein <=, wo < und == hingehört hätten, und jeder Zähler kürzester Wege wird 1.
• Eine Schranke ohne die Datenstruktur nennen. Binärer Heap, Fibonacci-Heap und Array liefern drei verschiedene Antworten, und der Interviewer will wissen, dass Sie das wissen.
• Nicht nach der Eingabe fragen. Gerichtet? Gewichte nichtnegativ? Kann das Ziel unerreichbar sein? Gibt es parallele Kanten mit unterschiedlichen Gewichten? Jede Antwort ändert den Code, und Skienas Punkt gilt: Probleme werden in der Modellierung gewonnen.

Die Gewohnheit, die die meisten davon verhindert: Sagen Sie vor dem Schreiben, was das Label bedeutet und warum das Verlängern einer Route es nie verbessern kann. Wenn Sie diesen Satz nicht sagen können, ist das Problem kein Dijkstra-Problem, und Sie haben sich gerade zwanzig Minuten gespart. McDowell argumentiert für Interviewprobleme allgemein genauso.

13. Literatur

Die Arbeiten, die diese Techniken eingeführt haben, und die Lehrbücher, die sie analysieren, in chronologischer Reihenfolge.

1. Bellman, R. (1958). “On a routing problem.” Quarterly of Applied Mathematics, 16(1), 87–90.
2. Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs.” Numerische Mathematik, 1, 269–271.
3. Williams, J. W. J. (1964). “Algorithm 232: Heapsort.” Communications of the ACM, 7(6), 347–348.
4. Hart, P. E., Nilsson, N. J. und Raphael, B. (1968). “A formal basis for the heuristic determination of minimum cost paths.” IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
5. Johnson, D. B. (1977). “Efficient algorithms for shortest paths in sparse networks.” Journal of the ACM, 24(1), 1–13.
6. Fredman, M. L. und Tarjan, R. E. (1987). “Fibonacci heaps and their uses in improved network optimization algorithms.” Journal of the ACM, 34(3), 596–615.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage, Abschnitt 24.3. MIT Press.
8. Sedgewick, R. und Wayne, K. (2011). Algorithms, 4. Auflage, Abschnitt 4.4. Addison-Wesley.
9. McDowell, G. L. (2015). Cracking the Coding Interview, 6. Auflage. CareerCup.
10. Skiena, S. S. (2020). The Algorithm Design Manual, 3. Auflage, Kapitel 8. Springer.