Dijkstra-Algorithmus: der kürzeste Weg in Python

Problem

Die wenigsten Straßen sind nicht die schnellste Route

Ein Kurier fährt vom Lager zu einem Kunden. Die App soll ihm die schnellste Route geben. Jede Straße hat eine Zeit in Minuten: Der Boulevard ist breit, aber verstopft, und die kleinen Seitenstraßen sind schnell.

Die Stadt ist ein Graph, und die Straßen sind seine Kanten in beide Richtungen (siehe Darstellung eines Graphen):

def add_street(city, a, b, minutes):
    city.setdefault(a, []).append((b, minutes))
    city.setdefault(b, []).append((a, minutes))

city = {}
add_street(city, "Lager", "Brücke", 2)
add_street(city, "Lager", "Platz", 5)
add_street(city, "Lager", "Markt", 15)
add_street(city, "Brücke", "Platz", 1)
add_street(city, "Brücke", "Bahnhof", 8)
add_street(city, "Platz", "Bahnhof", 3)
add_street(city, "Platz", "Markt", 9)
add_street(city, "Bahnhof", "Kunde", 3)
add_street(city, "Markt", "Kunde", 2)

Die erste Idee ist BFS aus der vorigen Lektion: Es findet den kürzesten Weg. Aber BFS zählt Straßen, nicht Minuten:

def fewest_streets(city, start):
    prev = {}
    seen = {start}
    queue = deque([start])
    while queue:
        place = queue.popleft()
        for to, _ in city[place]:
            if to not in seen:
                seen.add(to)
                prev[to] = place
                queue.append(to)
    return prev

city = {}
add_street(city, "Lager", "Brücke", 2)
add_street(city, "Lager", "Platz", 5)
add_street(city, "Lager", "Markt", 15)
add_street(city, "Brücke", "Platz", 1)
add_street(city, "Brücke", "Bahnhof", 8)
add_street(city, "Platz", "Bahnhof", 3)
add_street(city, "Platz", "Markt", 9)
add_street(city, "Bahnhof", "Kunde", 3)
add_street(city, "Markt", "Kunde", 2)
r = route(fewest_streets(city, "Lager"), "Kunde")
print(f"Wenigste Straßen: {' → '.join(r)} ({len(r) - 1} Straßen, {minutes(city, r)} Min.)")

Wenigste Straßen: Lager → Markt → Kunde (2 Straßen, 17 Min.)

Zwei Straßen, aber 17 Minuten: 15 den Boulevard entlang zum Markt und 2 zum Kunden. Über die Brücke, den Platz und den Bahnhof sind es vier Straßen und nur 9 Minuten. BFS schaut die Minuten gar nicht an.

Die Idee

Zuerst der nächste Ort

BFS geht nach der Anzahl der Straßen vor: zuerst alles, was eine Straße entfernt ist, dann zwei. Hier musst du nach Minuten vorgehen: zuerst der Ort, den du am schnellsten erreichst, dann der nächste.

Das ist der Dijkstra-Algorithmus (Edsger Dijkstra, 1956). Er merkt sich für jeden Ort die beste Zeit bisher, dist, und eine Warteschlange aus Einträgen „Minuten, Ort“.

Am Anfang ist dist für das Lager 0, und jeder andere Ort ist unerreicht (∞).
Nimm den Eintrag mit den wenigsten Minuten aus der Warteschlange. Das ist eine Prioritätswarteschlange: Sie entnimmt das Kleinste in O(log n).
Probiere für jede Straße von diesem Ort: Erreicht sie den Nachbarn schneller als bisher? Wenn ja, notiere die neue Zeit, merke dir, woher du gekommen bist (prev), und lege einen neuen Eintrag in die Warteschlange. Dieses Probieren heißt Relaxation (relaxation).
Wiederhole, bis die Warteschlange leer ist.

Warum hat der Ort, der die Warteschlange verlässt, schon seine endgültige Zeit? Alle anderen Einträge haben mindestens so viele Minuten, und jede Straße fügt Minuten hinzu. Kein Weg über sie kann früher ankommen.

Sieh es dir an

Dijkstra von innen

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # veraltet
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

heapq vergleicht Tupel von links nach rechts: (minutes, place) kommt nach Minuten heraus. Ein Ort, der in dist fehlt, ist noch nicht erreicht: Das ist ∞.

prev behält die Route rückwärts: für jeden Ort, woher der schnellste Weg kam. Du startest beim Kunden, folgst prev bis zum Lager und drehst das Ergebnis um:

def route(prev, end):
    places = []
    at = end
    while at is not None:
        places.append(at)
        at = prev.get(at)
    return places[::-1]

dist, prev = dijkstra(city, "Lager")
r = route(prev, "Kunde")
print(f"Am schnellsten: {' → '.join(r)} ({len(r) - 1} Straßen, {minutes(city, r)} Min.)")

Am schnellsten: Lager → Brücke → Platz → Bahnhof → Kunde (4 Straßen, 9 Min.)

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # veraltet
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

Schritt für Schritt, in Worten

Start des Kuriers: Lager, 0 Minuten. Jeder andere Ort ist ∞, noch nichts hat ihn erreicht. In der Warteschlange liegt ein einziger Eintrag: 0 Lager.
Der kleinste Eintrag wird genommen, 0 Lager. Jede Straße von dort liefert eine Zeit: Brücke 2, Platz 5, Markt 15. Alle sind besser als ∞: Sie werden notiert und kommen in die Warteschlange.
Als Nächstes 2 Brücke. Darüber ist Platz in 2 + 1 = 3 Minuten erreichbar, besser als 5: Zeit und prev ändern sich, 3 Platz kommt hinein. Das alte 5 Platz bleibt in der Warteschlange, es ist jetzt veraltet. Bahnhof bekommt 10.
3 Platz: endgültig, nichts in der Warteschlange kann es schneller machen. Darüber sinkt Bahnhof von 10 auf 6 und Markt von 15 auf 12.
Oben liegt 5 Platz, aber Platz hat schon 3. Der Eintrag ist veraltet: überspringen. Das ist das faule Löschen: Statt in der Warteschlange nach dem alten Eintrag zu suchen, wirfst du ihn weg, wenn er herauskommt.
6 Bahnhof: endgültig. Kunde bekommt 6 + 3 = 9. Der Weg zurück, Brücke mit 14 und Platz mit 9, ist nicht besser.
9 Kunde: endgültig, 9 Minuten. Über Kunde sinkt Markt von 12 auf 11. Die Grenze wächst nach Zeit, nicht nach Anzahl der Straßen.
Der Rest: 10 Bahnhof ist veraltet, 11 Markt ist endgültig und verbessert nichts, 12 und 15 Markt sind veraltet. Die Warteschlange ist leer.
prev liefert die Route rückwärts: Kunde ← Bahnhof ← Platz ← Brücke ← Lager. Umgedreht: Lager → Brücke → Platz → Bahnhof → Kunde, 9 Minuten, vier Straßen. Die Route mit zwei Straßen über Markt dauert 17.

Die Orte werden in der Reihenfolge ihrer Zeit endgültig: Lager 0, Brücke 2, Platz 3, Bahnhof 6, Kunde 9, Markt 11. Der Markt, eine Straße vom Lager entfernt, kommt zuletzt.

Probier es aus

Sag die Ausgabe voraus

Wie viele Minuten zum Markt gibt Dijkstra aus?

city = {}
add_street(city, "Lager", "Brücke", 2)
add_street(city, "Lager", "Platz", 5)
add_street(city, "Lager", "Markt", 15)
add_street(city, "Brücke", "Platz", 1)
add_street(city, "Brücke", "Bahnhof", 8)
add_street(city, "Platz", "Bahnhof", 3)
add_street(city, "Platz", "Markt", 9)
add_street(city, "Bahnhof", "Kunde", 3)
add_street(city, "Markt", "Kunde", 2)
dist, prev = dijkstra(city, "Lager")
print(dist["Markt"])

Antwort

Die Idee

Veraltete Einträge

Wenn der Platz 3 Minuten bekommt statt 5, liegt der Eintrag „5 Platz“ schon in der Warteschlange. Warum ändert man ihn nicht an Ort und Stelle?

Eingebaute Warteschlangen können das nicht: Pythons heapq sind nur Funktionen über einer Liste, ohne „Priorität ändern“. Also kommt die bessere Zeit als neuer Eintrag hinein. Der alte bleibt, und wenn er herauskommt, wirft ihn die Prüfung weg: Seine Zeit ist größer als die in dist. Das ist faules Löschen (lazy deletion).

Die Warteschlange kann mehr Einträge halten als Orte, höchstens einen pro Straße. Der Preis ist ein bisschen Speicher und ein paar leere Entnahmen.

minutes, place = heapq.heappop(queue)
if :
    continue  # veraltet

Probier es aus

Finde den Fehler

Ein Kollege hat entschieden, dass die erste gefundene Zeit auch die beste ist, wie bei BFS:

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # veraltet
        for to, length in city[place]:
            t = minutes + length
            if to not in dist:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

dist, prev = dijkstra(city, "Lager")
r = route(prev, "Kunde")
print(f"Am schnellsten: {' → '.join(r)} ({len(r) - 1} Straßen, {minutes(city, r)} Min.)")

Am schnellsten: Lager → Brücke → Bahnhof → Kunde (3 Straßen, 13 Min.)

13 Minuten statt 9. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Was es kostet

Jede Straße wird zweimal probiert (einmal von jedem Ende) und kann einen Eintrag hinzufügen. Jeder Eintrag kommt einmal hinein und einmal heraus, zu je O(log V). Insgesamt O((V + E) log V) für V Orte und E Straßen.

Ohne die Warteschlange findet man den nächsten Ort mit einer Schleife über alle Orte, die noch nicht endgültig sind. So wurde der Algorithmus ursprünglich geschrieben:

def dijkstra_scan(city, start):
    dist = {place: math.inf for place in city}
    dist[start] = 0
    done = set()
    while len(done) < len(city):
        best = None
        for place in city:
            if place not in done and (best is None or dist[place] < dist[best]):
                best = place
        if dist[best] == math.inf:
            break
        done.add(best)
        for to, length in city[best]:
            t = dist[best] + length
            if t < dist[to]:
                dist[to] = t
    return dist

city = {}
add_street(city, "Lager", "Brücke", 2)
add_street(city, "Lager", "Platz", 5)
add_street(city, "Lager", "Markt", 15)
add_street(city, "Brücke", "Platz", 1)
add_street(city, "Brücke", "Bahnhof", 8)
add_street(city, "Platz", "Bahnhof", 3)
add_street(city, "Platz", "Markt", 9)
add_street(city, "Bahnhof", "Kunde", 3)
add_street(city, "Markt", "Kunde", 2)
dist = dijkstra_scan(city, "Lager")
print(", ".join(f"{p} {dist[p]}" for p in ["Lager", "Brücke", "Platz", "Bahnhof", "Markt", "Kunde"]))

Lager 0, Brücke 2, Platz 3, Bahnhof 6, Markt 11, Kunde 9

Die Antwort ist dieselbe. Aber die Schleife hat V Schritte und läuft V-mal: O(V²).

Lass beide Versionen in einem Viertel laufen, in dem die Kreuzungen ein Gitter bilden und jede mit ihrem rechten und unteren Nachbarn verbunden ist. Jede Straße dauert 1 bis 9 Minuten. Gezählt wird jeder Vergleich zweier Zeiten: bei der Suche nach dem nächsten Ort, in der Warteschlange und beim Probieren einer Straße.

Ohne Warteschlange: eine Schleife für den nächsten O(n²)
Mit einer Prioritätswarteschlange O(n log n)

Algorithmus	n = 100	n = 1.000	n = 10.000	n = 100.000
Ohne Warteschlange: eine Schleife für den nächsten	5.410	504.372	≈ 50.437.200	≈ 5.043.720.000
Mit einer Prioritätswarteschlange	1.269	17.121	213.675	2.554.618

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # veraltet
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

Bei 1000 Kreuzungen macht die Version ohne Warteschlange 504.372 Vergleiche, die mit Warteschlange 17.121. Bei 100.000 Kreuzungen, der Größe einer großen Stadt, macht die Warteschlange 2.554.618. Ohne sie wären es etwa 5 Milliarden: Bench führt sie nicht aus, sondern schätzt sie anhand der Kurve.

Genauer, für Neugierige

Wann ist O(V²) besser? Wenn der Graph dicht ist: Jeder Ort ist mit fast jedem anderen verbunden, und E ist etwa V². Dann macht die Warteschlange O(V² log V) und die Schleife O(V²). In einem Straßennetz hat jede Kreuzung 3 bis 4 Straßen, der Graph ist dünn, und die Warteschlange gewinnt.

Negative Gewichte machen Dijkstra kaputt. Kostet eine Straße −5 (sagen wir, ein Lieferbonus auf dem Weg), kann ein Ort, der schon endgültig ist, später darüber näher werden, und der Algorithmus schaut ihn nicht mehr an. Für solche Graphen gibt es Bellman-Ford: Er probiert jede Straße V − 1 Mal, O(V · E), und meldet einen Zyklus, der die Zeit endlos senkt.

In Python ist ∞ math.inf: math.inf + 5 ist wieder math.inf, und ganze Zahlen laufen nicht über. In Java und C# ist ∞ meist das größte int, und Minuten dazuzuaddieren ergibt eine negative Zahl.

Die Navigation auf deinem Handy lässt Dijkstra nicht über einen ganzen Kontinent laufen. Sie nutzt A*: Dijkstra, das zu den Minuten in der Warteschlange eine Schätzung addiert, wie viel Luftlinie noch bleibt, und deshalb auf das Ziel zuhält, statt sich in alle Richtungen auszubreiten. OSPF, das Protokoll, mit dem Router in einem Netz den Weg der Pakete finden, lässt echtes Dijkstra laufen.

Übung

Eine gesperrte Straße

Löse die Aufgabe in deinem Editor.

Bauarbeiten. Die Straße zwischen der Brücke und dem Platz ist gesperrt. Entferne sie aus der Stadt (in beide Richtungen) und gib die schnellste Route und die Minuten zum Bahnhof, zum Kunden und zum Markt aus:

Bahnhof: Lager → Platz → Bahnhof (8 Min.)
Kunde: Lager → Platz → Bahnhof → Kunde (11 Min.)
Markt: Lager → Platz → Bahnhof → Kunde → Markt (13 Min.)

Der Markt ist wieder über den Kunden am schnellsten: 13 Minuten gegen 14 über den Platz und 15 den Boulevard entlang.

Weitere Aufgaben

Halte rechtzeitig an. Wenn dich nur der Kunde interessiert, halte an, sobald er die Warteschlange verlässt. Wie viele Einträge bleiben ungenommen?
Zähle die Entnahmen. Zähle, wie viele Einträge die Warteschlange verlassen haben und wie viele davon veraltet waren.
Zwei Kuriere. Zwei Lager, ein Kunde: Welcher Kurier ist zuerst da? Tipp: Lege beide Lager mit 0 Minuten in die Warteschlange.

Test

Teste dich

1. Warum findet BFS nicht die schnellste Route, wenn Straßen Minuten haben?BFS zählt Straßen: Es findet den Weg mit den wenigsten Straßen, und der kann langsamer seinBFS erreicht nicht jeden OrtBFS funktioniert nur bei Bäumen

2. Ein Ort verlässt die Warteschlange mit den wenigsten Minuten aller Einträge. Warum ist seine Zeit endgültig?Jeder andere Weg führt über einen Ort mit mindestens so vielen Minuten, und Straßen sind nicht negativWeil die Warteschlange nach der Anzahl der Straßen geordnet istWeil nichts auf ihn zeigt

3. In der Warteschlange liegt 5 Platz, und Platz hat schon 3 Minuten. Was macht der Algorithmus, wenn 5 Platz herauskommt?Er ändert die Zeit von Platz auf 5Er hält an: Ein Zyklus wurde gefundenEr überspringt ihn: Der Eintrag ist veraltet

4. Wie viel kostet Dijkstra mit einem binären Heap bei V Orten und E Straßen?O((V + E) log V)O(V + E)O(V²)

Dijkstra

Cookies