Dijkstra vs Bellman-Ford vs Floyd-Warshall

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Die kurze Antwort

Der Algorithmus von Dijkstra, der Bellman-Ford-Algorithmus und der Floyd-Warshall-Algorithmus finden alle kürzeste Wege in einem gewichteten Graphen, beantworten aber unterschiedliche Fragen unter unterschiedlichen Bedingungen. Zwei Fragen entscheiden zwischen ihnen: Brauchen Sie Distanzen von einer Quelle aus oder zwischen allen Paaren von Knoten? Und kann eine Kante ein negatives Gewicht haben?

Hier ist V die Anzahl der Knoten und E die Anzahl der Kanten. In einem Satz: Verwenden Sie Dijkstra standardmäßig, wechseln Sie zu Bellman-Ford, wenn Gewichte negativ sein können, und verwenden Sie Floyd-Warshall, wenn Sie die gesamte Distanztabelle eines Graphen mit höchstens einigen hundert Knoten brauchen. Wenn Sie alle Paare in einem großen dünnen Graphen mit negativen Kanten brauchen, kombiniert der Johnson-Algorithmus in Abschnitt 7 die ersten beiden. Der Rest dieses Leitfadens lässt alle drei auf demselben Graphen laufen und zeigt, wo jeder gewinnt und wo jeder scheitert.

2. Ein Graph, drei Antworten

Das durchgehende Beispiel ist ein kleiner gerichteter Graph mit sechs Knoten, sieben Kanten und einer negativen Kante, B → A mit Gewicht -4. Stellen Sie sich die Gewichte als Kosten vor: Negative Kosten sind eine Rückerstattung, etwa eine Mautstraße, die Sie dafür bezahlt, dass Sie sie benutzen, oder ein Schritt in einem chemischen Prozess, der Energie freisetzt.

S → A  3      S → B  6      A → C  4      B → A  -4
C → T  2      B → D  3      D → T  4

6 Knoten, 7 Kanten, keine Zyklen; Quelle S

Die günstigste Route von S nach T ist S, B, A, C, T, mit Kosten 6 - 4 + 4 + 2 = 8. Sie beginnt mit dem teureren ersten Schritt nach B und holt ihn über die Rückerstattung wieder herein. Das folgende Programm implementiert die drei Algorithmen in ihrer üblichen Lehrbuchform und startet sie alle im Knoten S.

import heapq
INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def dijkstra(adj, s):
    """Greedy: den nächstgelegenen offenen Knoten abschließen, nie wieder besuchen."""
    dist = {v: INF for v in adj}
    dist[s] = 0
    done, heap = set(), [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue                      # veralteter Heap-Eintrag
        done.add(u)
        for v, w in adj[u]:
            if v not in done and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def bellman_ford(adj, s):
    """Jede Kante relaxieren, Runde um Runde, bis sich nichts mehr ändert."""
    dist = {v: INF for v in adj}
    dist[s] = 0
    for _ in range(len(adj) - 1):
        changed = False
        for u in adj:
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    changed = True
        if not changed:
            break
    return dist

def floyd_warshall(adj):
    """Alle Paare: die Knoten einzeln nacheinander als Zwischenstationen zulassen."""
    d = {u: {v: 0 if u == v else INF for v in adj} for u in adj}
    for u in adj:
        for v, w in adj[u]:
            d[u][v] = min(d[u][v], w)
    for k in adj:
        for i in adj:
            for j in adj:
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

G = graph([('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
           ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)])
dj, bf, fw = dijkstra(G, 'S'), bellman_ford(G, 'S'), floyd_warshall(G)['S']
for v in G:
    print(v, dj[v], bf[v], fw[v], '' if dj[v] == bf[v] else '<- Dijkstra is wrong')
# S 0 0 0
# A 3 2 2 <- Dijkstra is wrong
# B 6 6 6
# C 7 6 6 <- Dijkstra is wrong
# T 9 8 8 <- Dijkstra is wrong
# D 9 9 9

Bellman-Ford und Floyd-Warshall liefern die wahren Distanzen. Dijkstra meldet 3 für A, 7 für C und 9 für T, alle zu hoch, und gibt dabei keinen Fehler aus: Die falschen Antworten sehen genau wie richtige aus. Abschnitt 4 erklärt, warum. Auf einem Graphen mit nichtnegativen Gewichten würden alle drei übereinstimmen, und der einzige Unterschied wäre die Geschwindigkeit.

3. Was jeder Algorithmus tut

Alle drei Algorithmen bauen auf einer einzigen Operation auf, der Relaxation. Jeder Knoten v trägt eine vorläufige Distanz dist[v], die bei unendlich beginnt, bei der Quelle bei 0. Die Relaxation der Kante u → v mit Gewicht w prüft, ob der Weg über u günstiger ist, und hält ihn in diesem Fall fest:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Eine vorläufige Distanz sinkt immer nur, und sie entspricht stets den Kosten einer tatsächlich existierenden Route. Die Algorithmen unterscheiden sich nur darin, welche Kanten sie relaxieren und in welcher Reihenfolge.

• Dijkstra hält die noch offenen Knoten in einer Prioritätswarteschlange. Er nimmt wiederholt den mit der kleinsten vorläufigen Distanz, erklärt diese Distanz für endgültig und relaxiert seine ausgehenden Kanten. Jeder Knoten wird einmal abgeschlossen und jede Kante einmal relaxiert. Edsger Dijkstra entwarf den Algorithmus 1956, nach eigener Aussage in etwa zwanzig Minuten, und veröffentlichte ihn 1959. Der Leitfaden zum Algorithmus von Dijkstra verfolgt ihn Schritt für Schritt.
• Bellman-Ford trifft keine Entscheidungen. Er relaxiert jede Kante in einer beliebigen festen Reihenfolge und wiederholt das. Ein kürzester Weg ohne Zyklen hat höchstens V - 1 Kanten, und nach Runde i ist jeder kürzeste Weg mit höchstens i Kanten gefunden, also genügen V - 1 Runden immer. Der Name verbindet Richard Bellman, der die rundenbasierte Methode 1958 veröffentlichte, mit Lester Ford, dessen Arbeit von 1956 die allgemeine Regel angab, Kanten so lange zu relaxieren, bis sich nichts mehr verbessert. Alfonso Shimbel und Edward Moore fanden in denselben Jahren äquivalente Methoden. Der Leitfaden zum Bellman-Ford-Algorithmus beweist die Schranke.
• Floyd-Warshall berechnet die ganze Tabelle auf einmal. Er lässt die Knoten einzeln nacheinander als Zwischenstationen zu: Nach Schritt k enthält der Eintrag [i][j] die günstigste Route von i nach j, deren Zwischenknoten alle aus den ersten k stammen. Drei verschachtelte Schleifen und eine Zeile Arithmetik. Bernard Roy (1959) und Stephen Warshall (1962) veröffentlichten dasselbe Schema für die Erreichbarkeit, und Robert Floyd übertrug es 1962 auf kürzeste Wege. Der Leitfaden zum Floyd-Warshall-Algorithmus leitet die Rekursion her.

Im Beispiel besucht Bellman-Ford die Kanten in der Reihenfolge, in der sie aufgelistet wurden. Schon seine erste Runde senkt A auf 2, wenn sie die Kanten erreicht, die von B ausgehen, aber bis dahin hat sie den alten Wert 3 bereits benutzt, um C = 7 zu setzen. Die zweite Runde trägt die Verbesserung weiter zu C = 6 und T = 8. Die dritte Runde ändert nichts, also hält der Algorithmus vorzeitig an, statt alle V - 1 = 5 Runden zu durchlaufen. Wie viele Runden nötig sind, hängt von der Kantenreihenfolge ab, überschreitet aber nie V - 1.

4. Warum Dijkstra an negativen Kanten scheitert

Die Geschwindigkeit von Dijkstra beruht auf einem Versprechen: Wenn ein Knoten die Prioritätswarteschlange verlässt, ist seine Distanz endgültig. Das Versprechen stützt sich auf ein Argument, das nichtnegative Gewichte braucht. Angenommen, u ist der nächstgelegene offene Knoten. Jede andere Route zu u muss den abgeschlossenen Bereich über einen offenen Knoten x verlassen, der bereits mindestens so weit entfernt ist wie u, und der Rest der Route kann nur Kosten hinzufügen. Mit einer negativen Kante kann der Rest der Route Kosten abziehen, und das Argument bricht zusammen.

Genau das passiert im Beispiel. Dijkstra schließt S bei 0 ab, dann A bei 3, weil 3 kleiner ist als die 6 von B. Dann wird B abgeschlossen, und seine Kante nach A bietet 6 - 4 = 2, A ist jedoch bereits endgültig, und die Verbesserung wird verworfen. Alles, was auf A aufbaut, erbt den Fehler: C wird bei 3 + 4 = 7 statt 6 abgeschlossen und T bei 9 statt 8.

Zwei naheliegende Korrekturen funktionieren nicht:

• Eine Konstante zu jedem Gewicht addieren. Wer 4 addiert, macht jedes Gewicht nichtnegativ, berechnet aber 4 für jede Kante, sodass Routen mit mehr Kanten stärker bestraft werden. Auf dem verschobenen Graphen findet Dijkstra S, A, C, T, mit verschobenen Kosten 21 gegenüber 24 für die wahre kürzeste Route S, B, A, C, T, die eine Kante mehr hat. In den ursprünglichen Gewichten kostet die gefundene Route 9, nicht 8. Der Johnson-Algorithmus in Abschnitt 7 zeigt die Umgewichtung, die tatsächlich funktioniert.
• Abgeschlossene Knoten wieder öffnen. Darf ein Knoten jedes Mal in die Warteschlange zurückkehren, wenn seine Distanz sinkt, wird der Algorithmus für negative Kanten korrekt, solange es keinen negativen Zyklus gibt. Aber das Versprechen, das ihn schnell machte, ist dahin, und Donald Johnson zeigte 1973, dass der auf diese Weise für negative Kanten angepasste Algorithmus von Dijkstra exponentielle Zeit brauchen kann, in der Größenordnung von n 2n Schritten auf einer Familie von Graphen mit n Knoten. Ab diesem Punkt ist das garantierte O(V E) von Bellman-Ford die sicherere Wahl.

Mit nichtnegativen Gewichten tritt nichts davon auf, und Dijkstra ist korrekt und der schnellste der drei. Gewichte von null sind kein Problem: Das Argument braucht nur, dass keine Kante die Kosten senkt.

5. Negative Zyklen

Ein negativer Zyklus ist ein Zyklus, dessen Gewichte sich zu weniger als null summieren. Ist er von der Quelle aus erreichbar und kann er das Ziel erreichen, gibt es überhaupt keine kürzeste Route: Eine weitere Runde durch den Zyklus ist immer günstiger. Die Distanz ist minus unendlich, und ein Algorithmus sollte den Zyklus melden statt einer Zahl. Fügen Sie die Kante C → B mit Gewicht -5 zum Beispiel hinzu, und der Zyklus B, A, C, B kostet -4 + 4 - 5 = -5.

• Bellman-Ford erkennt ihn mit einer zusätzlichen Runde. Ohne negativen Zyklus kann sich nach V - 1 Runden nichts mehr verbessern; senkt Runde V noch eine Distanz, existiert ein negativer Zyklus, und wer den Vorgängerzeigern vom geänderten Knoten aus rückwärts folgt, gelangt auf ihn.
• Floyd-Warshall erkennt ihn auf der Diagonale. Der Eintrag [v][v] beginnt bei 0 und kann nur negativ werden, wenn es eine geschlossene Route durch v mit negativem Gesamtgewicht gibt. Ein negativer Zyklus existiert also genau dann, wenn ein Diagonaleintrag am Ende unter null liegt. Sobald das geschieht, sind die anderen Einträge keine sinnvollen Distanzen mehr, und Stefan Hougardy zeigte 2010, dass sie exponentiell groß werden können. Am sichersten ist es daher, die Diagonale innerhalb der Schleife zu prüfen und anzuhalten, sobald ein Eintrag negativ wird.
• Dijkstra kann ihn nicht erkennen. Er nimmt einfach an, dass es ihn nicht gibt.

INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def negative_cycle(adj):
    """Bellman-Ford von einer virtuellen Quelle aus, die mit Kosten 0 mit jedem Knoten verbunden ist.
    Gibt einen negativen Zyklus als Liste von Knoten zurück, sonst None."""
    dist = {v: 0 for v in adj}
    parent = {v: None for v in adj}
    for _ in range(len(adj)):                  # eine Runde mehr als üblich
        last = None
        for u in adj:
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v], parent[v], last = dist[u] + w, u, v
        if last is None:
            return None                        # eine ruhige Runde: kein negativer Zyklus
    for _ in range(len(adj)):                  # weit genug zurückgehen, um auf dem Zyklus zu landen
        last = parent[last]
    cycle, v = [last], parent[last]
    while v != last:                           # den Vorgängern einmal rund um den Zyklus folgen
        cycle.append(v)
        v = parent[v]
    cycle.reverse()                            # Vorgänger zeigen rückwärts
    return cycle + cycle[:1]

def floyd_warshall_diagonal(adj):
    """Knoten, deren Distanz zu sich selbst negativ ausfällt."""
    d = {u: {v: 0 if u == v else INF for v in adj} for u in adj}
    for u in adj:
        for v, w in adj[u]:
            d[u][v] = min(d[u][v], w)
    for k in adj:
        for i in adj:
            for j in adj:
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return [v for v in adj if d[v][v] < 0]

edges = [('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
         ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)]
print(negative_cycle(graph(edges)))
# None
bad = graph(edges + [('C', 'B', -5)])          # B -> A -> C -> B kostet -4 + 4 - 5 = -5
print(negative_cycle(bad))
# ['C', 'B', 'A', 'C']
print(floyd_warshall_diagonal(bad))
# ['A', 'B', 'C']

Die Funktion startet Bellman-Ford von einer virtuellen Quelle aus, die mit Kosten 0 mit jedem Knoten verbunden ist, und findet so einen negativen Zyklus irgendwo im Graphen, nicht nur einen, der von S aus erreichbar ist. Im ursprünglichen Beispiel ändert irgendwann eine Runde nichts mehr, und sie gibt None zurück. Mit der zusätzlichen Kante gibt sie den Zyklus C, B, A, C zurück, denselben Zyklus von einem anderen Start aus geschrieben, und Floyd-Warshall markiert A, B und C auf seiner Diagonale. In Tests mit Tausenden zufälliger Graphen markierte die Diagonale genau dann einen negativen Zyklus, wenn einer existierte, markierte aber nicht immer jeden Knoten, der einen erreichen kann. Verwenden Sie sie also als Ja-Nein-Test.

Eine Falle erwischt viele. In einem ungerichteten Graphen kann eine Kante in beide Richtungen begangen werden, also ist schon eine einzelne Kante mit negativem Gewicht ein negativer Zyklus: u, v, u. Bellman-Ford auf der gerichteten Version eines ungerichteten Graphen meldet daher einen negativen Zyklus, sobald irgendeine Kante negativ ist, eine Falle, die Sedgewick und Wayne in Algorithms ausdrücklich beschreiben. Kürzeste einfache Wege mit negativen Gewichten in ungerichteten Graphen erfordern andere, aufwendigere Methoden.

6. Geschwindigkeit: welcher schneller ist und wann

Für eine einzelne Quelle ist die Reihenfolge klar, wann immer Dijkstra anwendbar ist: O((V + E) log V) mit binärem Heap gegenüber O(V E) bei Bellman-Ford. Auf einem Graphen mit 10.000 Knoten und 50.000 Kanten sind das grob eine Million Heap-Schritte gegenüber bis zu 500 Millionen Kantenrelaxationen. Floyd-Warshall ist kein Verfahren für eine einzelne Quelle, und wer es für eine Quelle laufen lässt, verschwendet fast seine gesamte Arbeit.

Für alle Paare ist der Vergleich knapper, denn die Alternativen bestehen darin, ein Verfahren für eine einzelne Quelle (Single-Source) von jedem Knoten aus zu starten:

Asymptotische Schranken verbergen Konstanten, deshalb zählt das folgende Programm die elementaren Schritte, die jedes Verfahren tatsächlich ausführt, auf zwei zufälligen gerichteten Graphen mit 100 Knoten: einem dünnen mit 300 Kanten und einem dichten mit 4.950, der Hälfte aller möglichen Kanten. Bei Dijkstra zählt es Kantenprüfungen und Heap-Operationen getrennt, da eine Heap-Operation etwa log V Schritte kostet.

import heapq, random
INF = float('inf')

def random_graph(n, m, seed):
    """n Knoten, m verschiedene gerichtete Kanten mit Gewichten 1..100."""
    rnd = random.Random(seed)
    pairs = rnd.sample([(u, v) for u in range(n) for v in range(n) if u != v], m)
    adj = {v: [] for v in range(n)}
    for u, v in pairs:
        adj[u].append((v, rnd.randint(1, 100)))
    return adj

def all_pairs_dijkstra(adj):
    """Dijkstra von jedem Knoten aus. Zählt Kantenprüfungen und Heap-Operationen."""
    checks = heap_ops = 0
    for s in adj:
        dist, heap = {v: INF for v in adj}, [(0, s)]
        dist[s] = 0
        while heap:
            d, u = heapq.heappop(heap)
            heap_ops += 1
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                checks += 1
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
                    heap_ops += 1
    return checks, heap_ops

def all_pairs_bellman_ford(adj):
    """Bellman-Ford von jedem Knoten aus, mit vorzeitigem Abbruch, wenn eine Runde nichts ändert."""
    m, checks = sum(len(a) for a in adj.values()), 0
    for s in adj:
        dist = {v: INF for v in adj}
        dist[s] = 0
        for _ in range(len(adj) - 1):
            changed = False
            for u in adj:
                for v, w in adj[u]:
                    if dist[u] + w < dist[v]:
                        dist[v], changed = dist[u] + w, True
            checks += m
            if not changed:
                break
    return checks

n = 100
for name, m in [('sparse', 3 * n), ('dense', n * (n - 1) // 2)]:
    adj = random_graph(n, m, seed=1)
    checks, heap_ops = all_pairs_dijkstra(adj)
    print(f'{name:6} E={m:4}  Dijkstra x V: {checks:7,} checks + {heap_ops:6,} heap ops   '
          f'Bellman-Ford x V: {all_pairs_bellman_ford(adj):9,}   Floyd-Warshall: {n ** 3:,}')
# sparse E= 300  Dijkstra x V:  27,565 checks + 21,388 heap ops   Bellman-Ford x V:   226,200   Floyd-Warshall: 1,000,000
# dense  E=4950  Dijkstra x V: 495,000 checks + 64,770 heap ops   Bellman-Ford x V: 2,712,600   Floyd-Warshall: 1,000,000

Auf dem dünnen Graphen braucht Dijkstra von jedem Knoten aus etwa 49.000 Schritte gegenüber den festen 1.000.000 von Floyd-Warshall, ein Faktor von etwa 20. Auf dem dichten Graphen schließt sich die Lücke fast, und sobald die logarithmischen Kosten pro Heap-Operation mitgezählt werden, gewinnt in der Praxis oft die einfache innere Schleife von Floyd-Warshall, die den Speicher der Reihe nach durchläuft und keine Prioritätswarteschlange braucht. Bellman-Ford von jedem Knoten aus ist in beiden Fällen am langsamsten, selbst mit vorzeitigem Abbruch. Die Faustregel: Unter einigen hundert Knoten oder wenn die meisten Knotenpaare durch eine Kante verbunden sind, verwenden Sie Floyd-Warshall wegen seiner Einfachheit; auf großen dünnen Graphen verwenden Sie Dijkstra oder Johnson von jedem Knoten aus.

7. Alle Paare mit negativen Kanten: der Johnson-Algorithmus

Donald Johnsons Algorithmus von 1977 vereint das Beste aus beiden. Er lässt Bellman-Ford einmal laufen, um für jeden Knoten eine Zahl h(v) zu berechnen, die Distanz von einer virtuellen Quelle aus, die mit Kosten 0 mit allen Knoten verbunden ist. Dann ersetzt er jedes Gewicht durch

w'(u, v) = w(u, v) + h(u) - h(v)

Weil h die Bedingung h(v) ≤ h(u) + w(u, v) für jede Kante erfüllt, ist jedes neue Gewicht nichtnegativ. Und entlang jeder Route von s nach t heben sich die Terme teleskopartig auf, sodass sich die Kosten jeder Route um denselben Betrag ändern, h(s) - h(t). Kürzeste Routen bleiben kürzeste, und Dijkstra kann nun von jedem Knoten aus laufen. Anders als das Addieren einer Konstanten hängt diese Umgewichtung nicht davon ab, wie viele Kanten eine Route hat.

import heapq
INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def dijkstra(adj, s):
    dist, heap = {v: INF for v in adj}, [(0, s)]
    dist[s] = 0
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def johnson(adj):
    """Alle Paare mit negativen Kanten: einmal Bellman-Ford, dann Dijkstra von jedem Knoten aus."""
    h = {v: 0 for v in adj}                    # Distanzen von einer virtuellen Quelle aus
    for _ in range(len(adj)):
        for u in adj:
            for v, w in adj[u]:
                h[v] = min(h[v], h[u] + w)
    for u in adj:
        for v, w in adj[u]:
            if h[u] + w < h[v]:
                raise ValueError('negative cycle')
    # umgewichten: jede Kante wird nichtnegativ, jeder Weg ändert sich um h[s] - h[t]
    lifted = {u: [(v, w + h[u] - h[v]) for v, w in adj[u]] for u in adj}
    return {s: {t: d - h[s] + h[t] for t, d in dijkstra(lifted, s).items()} for s in adj}, lifted

G = graph([('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
           ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)])
dist, lifted = johnson(G)
print({u: [(v, w) for v, w in lifted[u]] for u in ('S', 'A', 'B')})
# {'S': [('A', 7), ('B', 6)], 'A': [('C', 0)], 'B': [('A', 0), ('D', 3)]}
print(dist['S'])
# {'S': 0, 'A': 2, 'B': 6, 'C': 6, 'T': 8, 'D': 9}
print(dist['B'])
# {'S': inf, 'A': -4, 'B': 0, 'C': 0, 'T': 2, 'D': 3}

Im Beispiel gilt h(A) = -4, und jeder andere Knoten erhält 0. Die negative Kante B → A wird zu 0, S → A steigt von 3 auf 7 und A → C fällt von 4 auf 0, und Dijkstra auf den neuen Gewichten, zurückkorrigiert um h, liefert die wahren Distanzen von jeder Quelle aus, einschließlich der Zeile für B mit ihrem negativen Eintrag -4. Findet Bellman-Ford im ersten Schritt einen negativen Zyklus, hält der Johnson-Algorithmus an und meldet ihn.

8. Wenn keiner der drei die beste Wahl ist

Manche Graphen haben eine Struktur, die eine einfachere oder schnellere Methode ausnutzen kann:

• Ungewichtete Graphen. Zählt jede Kante als 1, findet die Breitensuche alle Distanzen von einer Quelle aus in O(V + E). Dijkstra würde dieselbe Antwort langsamer liefern. Siehe BFS vs DFS.
• Azyklische Graphen. Verarbeiten Sie in einem gerichteten azyklischen Graphen (DAG) die Knoten in topologischer Reihenfolge und relaxieren Sie die ausgehenden Kanten jedes Knotens einmal. Das dauert O(V + E) und funktioniert mit negativen Gewichten. Der Beispielgraph hat keine Zyklen, also hätte diese Methode ihn in einem einzigen Durchlauf gelöst.
• Nur Gewichte 0 und 1. Eine doppelseitige Warteschlange ersetzt die Prioritätswarteschlange: Kanten mit Gewicht 0 kommen nach vorn, Kanten mit Gewicht 1 nach hinten, was lineare Zeit ergibt.
• Eine Quelle und ein Ziel mit einer guten Schätzung. Die A*-Suche addiert eine Schätzung der verbleibenden Distanz zur Priorität von Dijkstra und erkundet auf Karten weit weniger Knoten. Mehr dazu im Leitfaden zum A*-Suchalgorithmus.

9. Speicher und das Rekonstruieren der Wege

Distanzen reichen oft nicht: Sie wollen die Route selbst. Dijkstra und Bellman-Ford speichern einen Vorgänger pro Knoten, den Knoten, von dem die beste Route kam, und die Route nach t wird rückwärts ab t gelesen. Das kostet O(V) zusätzlichen Speicher. Floyd-Warshall braucht neben seiner Distanztabelle eine vollständige V mal V große Tabelle mit Einträgen für den „nächsten Hop“, also liegt sein Speicherbedarf bei O(V2). Bei 10.000 Knoten mit 8-Byte-Einträgen belegt allein die Distanztabelle etwa 800 Megabyte, und die Tabelle der nächsten Hops braucht noch einmal genauso viel. Meist ist es der Speicher, mehr als die Zeit, der Floyd-Warshall auf großen Graphen ausschließt.

10. Wo welcher Algorithmus eingesetzt wird

• Dijkstra ist überall dort der Standard, wo Kosten physikalisch sind: Straßennavigation, Flugverbindungen und die Link-State-Routingprotokolle des Internets wie OSPF, bei denen jeder Router kürzeste Wege über eine Karte des Netzwerks berechnet.
• Bellman-Ford passt zu Umgebungen, in denen jeder Knoten nur seine Nachbarn kennt. Distanzvektor-Routingprotokolle wie RIP wiederholen seinen Relaxationsschritt über das Netzwerk hinweg, wobei jeder Router seine Tabelle aus den Tabellen seiner Nachbarn aktualisiert. Seine Fähigkeit, negative Zyklen zu finden, wird genutzt, um Währungsarbitrage zu erkennen: Mit den Gewichten -log(rate) ist eine Folge von Tauschgeschäften, die mit mehr Geld endet, als sie begann, genau ein negativer Zyklus.
• Floyd-Warshall füllt vollständige Distanztabellen für kleine Graphen: Distanzmatrizen für das Clustering oder das Problem des Handlungsreisenden, und die transitive Hülle, also die Frage, welche Knoten welche erreichen können, in der Version, die Warshall veröffentlichte.

11. Immer noch ein aktives Forschungsgebiet

Kürzeste Wege gehören zu den ältesten Problemen der Algorithmik, und die Schranken bewegen sich noch immer. 2022 zeigten Aaron Bernstein, Danupon Nanongkai und Christian Wulff-Nilsen, dass kürzeste Wege von einer Quelle aus mit negativen ganzzahligen Gewichten in nahezu linearer Zeit lösbar sind, weit unter dem O(V E) von Bellman-Ford. 2024 bewiesen Bernhard Haeupler und Koautoren, dass der Algorithmus von Dijkstra mit einem geeignet entworfenen Heap universell optimal für das Ordnen von Knoten nach Distanz ist: Auf jedem festen Graphen liegt sein schlechtester Fall über alle Kantengewichte innerhalb eines konstanten Faktors des Besten, was irgendein Algorithmus leisten kann. Und 2025 stellten Ran Duan und Koautoren einen deterministischen Algorithmus für gerichtete Graphen mit nichtnegativen Gewichten vor, der in O(E log2/3 V) Zeit läuft und auf dünnen Graphen das O(E + V log V) von Dijkstra schlägt. Er überwindet, was lange als Sortierschranke galt, weil er, anders als Dijkstra, die Knoten nicht in der Reihenfolge ihrer Distanz ausgibt. Jede der drei Arbeiten gewann einen Best-Paper-Award. Keiner dieser Algorithmen hat die drei Klassiker bisher im Alltagscode ersetzt, wo Einfachheit und kleine Konstanten mehr zählen.

12. Häufige Fehler

13. Glossar

15. Quellen

Die Algorithmen, Schranken und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Shimbel, A. (1955). "Structure in Communication Nets." In Proceedings of the Symposium on Information Networks, 199 bis 203. Brooklyn: Polytechnic Press of the Polytechnic Institute of Brooklyn.
2. Ford, L. R. (1956). Network Flow Theory. Paper P-923. Santa Monica: RAND Corporation.
3. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 bis 90.
4. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1, 269 bis 271.
5. Moore, E. F. (1959). "The Shortest Path Through a Maze." In Proceedings of an International Symposium on the Theory of Switching, 285 bis 292. Cambridge, MA: Harvard University Press.
6. Roy, B. (1959). "Transitivité et connexité." Comptes Rendus de l'Académie des Sciences 249, 216 bis 218.
7. Floyd, R. W. (1962). "Algorithm 97: Shortest Path." Communications of the ACM 5(6), 345.
8. Warshall, S. (1962). "A Theorem on Boolean Matrices." Journal of the ACM 9(1), 11 bis 12.
9. Johnson, D. B. (1973). "A Note on Dijkstra's Shortest Path Algorithm." Journal of the ACM 20(3), 385 bis 388.
10. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1 bis 13.
11. 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 bis 615.
12. Moy, J. (1998). "OSPF Version 2." RFC 2328. Internet Engineering Task Force.
13. Malkin, G. (1998). "RIP Version 2." RFC 2453. Internet Engineering Task Force.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, MA: MIT Press.
15. Frana, P. L. und Misa, T. J. (2010). "An Interview with Edsger W. Dijkstra." Communications of the ACM 53(8), 41 bis 47.
16. Hougardy, S. (2010). "The Floyd-Warshall Algorithm on Graphs with Negative Cycles." Information Processing Letters 110(8 bis 9), 279 bis 281.
17. Sedgewick, R. und Wayne, K. (2011). Algorithms, 4. Auflage. Upper Saddle River, NJ: Addison-Wesley.
18. Schrijver, A. (2012). "On the History of the Shortest Path Problem." Documenta Mathematica, Extra Volume ISMP, 155 bis 167.
19. Bernstein, A., Nanongkai, D. und Wulff-Nilsen, C. (2022). "Negative-Weight Single-Source Shortest Paths in Near-linear Time." Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science, 600 bis 611.
20. Haeupler, B., Hladík, R., Rozhoň, V., Tarjan, R. E. und Tětek, J. (2024). "Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps." Proceedings of the 65th IEEE Symposium on Foundations of Computer Science, 2099 bis 2130.
21. Duan, R., Mao, J., Mao, X., Shu, X. und Yin, L. (2025). "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." Proceedings of the 57th ACM Symposium on Theory of Computing, 36 bis 44.