Navigation in der Stadt mit BFS und Dijkstra in Python

Problem

Der Kurier fragt nach einer Route

Der Kurierdienst aus dem Modul „Graphen“ hat ein Lager in der Stadt. Die Karte ist eine Textdatei mit einer Straße pro Zeile: von wo, nach wo und wie viele Minuten man darauf fährt. - ist eine Straße in beide Richtungen, -> eine Einbahnstraße:

Lager - Bahnhof 4
Lager - Markt 3
Bahnhof - Platz 3
Markt - Platz 2
Markt -> Park 4
Platz - Kino 5
Kino - Krankenhaus 3
Park - Stadion 2
Stadion - Krankenhaus 2
Lager - Stadion 16

Der Disponent braucht eine Route vom Lager zum Krankenhaus. Der Kurier auf dem Fahrrad fragt nach der Route mit den wenigsten Kreuzungen, denn an jeder hält er an. Der Kurier im Lieferwagen fragt nach der schnellsten. Die Antworten sind nicht dieselben.

Dieses Projekt ist das Programm, das die Karte liest und beide Fragen beantwortet. Du baust es in Schritten, jeder mit einer Ausgabe, mit der du deine vergleichen kannst.

Die Idee

Der Plan

Die Karte als Graph. Kreuzungen sind Knoten, Straßen sind Kanten mit Gewicht: den Minuten. Wie in „Graph: Adjazenzliste und Matrix“ hältst du eine Adjazenzliste: eine Map von einer Kreuzung zu einer Liste von Straßen.
Wenigste Straßen. BFS vom Lager aus in Schichten: zuerst die Kreuzungen, die eine Straße entfernt sind, dann zwei.
Die Minuten einer Route. Die Summe der Minuten ihrer Straßen, um die beiden Antworten zu vergleichen.
Am schnellsten. Dijkstra mit einer Prioritätswarteschlange: Sie nimmt immer die Kreuzung mit den bisher wenigsten Minuten heraus.
Der Rückweg. Dasselbe Programm vom Krankenhaus zum Lager. Die Einbahnstraße macht den Rückweg anders.

Das Programm liest die Karte von der Standardeingabe, damit es mit jeder Karte funktioniert. Du startest es mit der Datei: python3 main.py < map.txt.

Übung

Schritt 1: die Karte

Lies die Karte in eine Map von einer Kreuzung zu einer Liste von Straßen (zu welcher Kreuzung und wie viele Minuten). Eine Straße in beide Richtungen kommt in die Listen beider Enden, eine Einbahnstraße nur in die Liste ihres Anfangs. Eine Kreuzung ohne ausgehende Straßen muss ebenfalls in der Map sein, mit einer leeren Liste.

Gib die Zahl der Kreuzungen und die Nachbarn von Lager, Markt und Park aus, in der Reihenfolge der Zeilen in der Datei:

Kreuzungen: 8
Lager: Bahnhof 4, Markt 3, Stadion 16
Markt: Lager 3, Platz 2, Park 4
Park: Stadion 2

Lösung

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


def read_map(text):
    city = {}
    for line in text.strip().splitlines():
        a, kind, b, minutes = line.split()
        add_street(city, a, b, int(minutes), kind == "-")
    return city


def neighbors(city, place):
    return f"{place}: " + ", ".join(f"{to} {m}" for to, m in city[place])


city = read_map(sys.stdin.read())
print(f"Kreuzungen: {len(city)}")
print(neighbors(city, "Lager"))
print(neighbors(city, "Markt"))
print(neighbors(city, "Park"))

Ganz oben steht import sys (später auch heapq und deque).

Der Park hat einen Nachbarn, das Stadion: Markt -> Park ist eine Einbahnstraße, und der Markt steht nicht in der Liste des Parks.

Übung

Schritt 2: wenigste Straßen

Schreibe fewestStreets(city, start, end): ein BFS von start, das anhält, sobald es end herausnimmt, und die Route als Liste von Kreuzungen zurückgibt. Um die Route zu bauen, merke dir für jede Kreuzung, woher du gekommen bist (prev), gehe dann von end rückwärts und drehe die Liste um.

wenigste Straßen: Lager → Stadion → Krankenhaus

Lösung

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


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


city = read_map(sys.stdin.read())
print(f"wenigste Straßen: {" → ".join(fewest_streets(city, "Lager", "Krankenhaus"))}")

Eine Kreuzung wird als gesehen markiert, wenn sie in die Warteschlange kommt, nicht wenn sie herauskommt: Sonst kommt eine Kreuzung mehrmals hinein.

Übung

Schritt 3: wie viele Minuten

Füge minutesOf(city, route) hinzu, das die Minuten der Straßen entlang der Route addiert, und describe(city, route), das die Route, die Zahl der Straßen und die Minuten zurückgibt. Gib die Route aus Schritt 2 mit describe aus:

wenigste Straßen: Lager → Stadion → Krankenhaus (2 Straßen, 18 Min.)

Lösung

def minutes_of(city, route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(m for to, m in city[a] if to == b)
    return total


def describe(city, route):
    return f"{' → '.join(route)} ({len(route) - 1} Straßen, {minutes_of(city, route)} Min.)"


city = read_map(sys.stdin.read())
print(f"wenigste Straßen: {describe(city, fewest_streets(city, "Lager", "Krankenhaus"))}")

Zwei Straßen, aber 18 Minuten: sechzehn davon auf der Ringstraße.

Sieh es dir an

Zwei Routen auf einer Karte

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

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

Schritt für Schritt, in Worten

Die Karte: 8 Kreuzungen und 10 Straßen mit ihren Minuten. Markt → Park ist eine Einbahnstraße, die Ringstraße von Lager bis Stadion dauert 16 Min.
BFS, eine Straße von Lager entfernt: Bahnhof, Markt, Stadion. Die Minuten interessieren ihn nicht.
Zwei Straßen entfernt: Platz, Park, Krankenhaus. Krankenhaus ist schon in der Warteschlange, über Stadion.
Wenigste Straßen: Lager → Stadion → Krankenhaus, 2 Straßen, aber 18 Min.: 16 davon sind die Ringstraße.
Dijkstra: Die Warteschlange ist nach Minuten geordnet. Lager 0, seine Nachbarn kommen in die Warteschlange: Bahnhof 4, Markt 3, Stadion 16.
Das Schnellste in der Warteschlange ist Markt, 3 Min. Neu: Platz 5, Park 7.
Bahnhof, 4 Min.: darüber wird nichts schneller.
Das Schnellste in der Warteschlange ist Platz, 5 Min. Neu: Kino 10.
Park mit 7 Min. Darüber sinkt Stadion von 16 auf 9.
Das Schnellste in der Warteschlange ist Stadion, 9 Min. Neu: Krankenhaus 11.
Kino, 10 Min.: darüber wird nichts schneller.
Krankenhaus kommt mit 11 Min. heraus: nichts in der Warteschlange ist schneller, also ist das die Antwort.
Am schnellsten: Lager → Markt → Park → Stadion → Krankenhaus, 4 Straßen, 11 Min.
Zwei Antworten auf zwei Fragen: 2 Straßen und 18 Min. oder 4 Straßen und 11 Min. Für den Kurier zählen die Minuten.

BFS sieht nur die Zahl der Straßen und wählt die Ringstraße. Dijkstra nimmt die Kreuzungen nach Minuten heraus und erreicht das Krankenhaus in 11 Min. über den Markt, die Einbahnstraße und das Stadion. Das Stadion hat zuerst 16 Min. über die Ringstraße, dann sinkt es über den Park auf 9.

Übung

Schritt 4: am schnellsten

Schreibe fastest(city, start, end) mit Dijkstra: dist hält die bisher wenigsten Minuten, die Warteschlange ist nach Minuten geordnet, und prev hält die Route. Gib beide Routen aus:

wenigste Straßen: Lager → Stadion → Krankenhaus (2 Straßen, 18 Min.)
am schnellsten: Lager → Markt → Park → Stadion → Krankenhaus (4 Straßen, 11 Min.)

Lösung

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


city = read_map(sys.stdin.read())
print(f"wenigste Straßen: {describe(city, fewest_streets(city, "Lager", "Krankenhaus"))}")
print(f"am schnellsten: {describe(city, fastest(city, "Lager", "Krankenhaus"))}")

heapq hält die Liste als Heap. Die Einträge sind Paare (Minuten, Kreuzung): Tupel werden zuerst nach den Minuten verglichen.

Probier es aus

Ergänze

Eine Kreuzung kann mehrmals in die Warteschlange kommen, wenn die Minuten bis zu ihr sinken. Der alte Eintrag bleibt. Was macht das Programm, wenn es ihn herausnimmt?

if minutes > dist[at]:

Probier es aus

Sag den Rückweg voraus

Der Kurier kehrt vom Krankenhaus zum Lager zurück. Das Programm fragt fastest(city, "Krankenhaus", "Lager"). Was gibt es aus?

city = read_map(sys.stdin.read())
print(f"zurück: {describe(city, fastest(city, "Krankenhaus", "Lager"))}")

Antwort

zurück: Krankenhaus → Stadion → Lager (2 Straßen, 18 Min.)

zurück: Krankenhaus → Stadion → Park → Markt → Lager (4 Straßen, 11 Min.)

zurück: Krankenhaus → Kino → Platz → Markt → Lager (4 Straßen, 13 Min.)

Übung

Schritt 5: das ganze Programm

Füge den Rückweg hinzu. Das ganze Programm gibt aus:

wenigste Straßen: Lager → Stadion → Krankenhaus (2 Straßen, 18 Min.)
am schnellsten: Lager → Markt → Park → Stadion → Krankenhaus (4 Straßen, 11 Min.)
zurück: Krankenhaus → Kino → Platz → Markt → Lager (4 Straßen, 13 Min.)

Das ganze Programm

import heapq
import sys
from collections import deque


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


def read_map(text):
    city = {}
    for line in text.strip().splitlines():
        a, kind, b, minutes = line.split()
        add_street(city, a, b, int(minutes), kind == "-")
    return city


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


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


def minutes_of(city, route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(m for to, m in city[a] if to == b)
    return total


def describe(city, route):
    return f"{' → '.join(route)} ({len(route) - 1} Straßen, {minutes_of(city, route)} Min.)"


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


city = read_map(sys.stdin.read())
print(f"wenigste Straßen: {describe(city, fewest_streets(city, "Lager", "Krankenhaus"))}")
print(f"am schnellsten: {describe(city, fastest(city, "Lager", "Krankenhaus"))}")
print(f"zurück: {describe(city, fastest(city, "Krankenhaus", "Lager"))}")

Probier es aus

Finde den Fehler

Ein Kollege hat addStreet gekürzt. Jetzt kommt der Rückweg mit 11 Min. heraus:

zurück: Krankenhaus → Stadion → Park → Markt → Lager (4 Straßen, 11 Min.)

Wähle die Zeile mit dem Fehler.

Sieh es dir an

Miss: die Stadt wächst

Eine echte Stadt hat Tausende Kreuzungen. Das Raster ist ein Geschwindigkeitstest: n Kreuzungen in einem Quadrat, Straßen zwischen Nachbarn, Minuten nach einer Formel. Der Kurier startet in der oberen linken Ecke und fährt zur unteren rechten:

def grid_city(size):
    city = {}
    for r in range(size):
        for c in range(size):
            at = f"{r}:{c}"
            if c + 1 < size:
                add_street(city, at, f"{r}:{c + 1}", 1 + (r * 7 + c * 13) % 9, True)
            if r + 1 < size:
                add_street(city, at, f"{r + 1}:{c}", 1 + (r * 11 + c * 5) % 9, True)
    return city


city = grid_city(100)
print(f"Kreuzungen: {len(city)}")
few = fewest_streets(city, "0:0", "99:99")
print(f"wenigste Straßen: {len(few) - 1} Straßen, {minutes_of(city, few)} Min.")
fast = fastest(city, "0:0", "99:99")
print(f"am schnellsten: {minutes_of(city, fast)} Min.")

Kreuzungen: 10000
wenigste Straßen: 198 Straßen, 990 Min.
am schnellsten: 693 Min.

Lass beide Algorithmen im Browser laufen. BFS sieht sich jede Straße einmal an: O(n). Dijkstra auch, aber jeder Eintrag im Heap kostet O(log n): O(n log n). Bei n = 1000 sind das 3.966 gegen 15.778 Operationen, und bei n = 100.000 sind es 398.158 gegen 2.348.779:

BFS: die wenigsten Straßen O(n)
Dijkstra: am schnellsten O(n log n)

Algorithmus	n = 10	n = 1.000	n = 100.000
BFS: die wenigsten Straßen	22	3.966	398.158
Dijkstra: am schnellsten	34	15.778	2.348.779

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 fastest(city, start, end):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, at = heapq.heappop(queue)
        if minutes > dist[at]:
            continue
        if at == end:
            return route(prev, end)
        for to, length in city[at]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = at
                heapq.heappush(queue, (t, to))
    return []

Genauer, für Neugierige

Dijkstra ist langsamer, aber es beantwortet die Frage nach den Minuten, und BFS kann das nicht. Beide halten an, sobald sie das Ziel herausnehmen: Bei einem nahen Ziel sehen sie sich nur einen kleinen Teil der Stadt an.

Navigation für ganze Länder lässt nicht von jedem Ort aus ein einfaches Dijkstra laufen. Sie verarbeitet die Karte vorab (zum Beispiel mit Contraction Hierarchies) und sucht mit A*, das eine Schätzung hinzufügt, wie weit das Ziel noch entfernt ist. Die Grundlage bleibt Dijkstra.

Übung

Straßenbau

Löse diese Aufgabe in deinem Editor.

Eine gesperrte Straße. Die Straße Park – Stadion ist wegen Bauarbeiten gesperrt. Gib readMap eine Menge gesperrter Straßen ("Park Stadion"), die diese Zeilen in beide Richtungen überspringt. Gib beide Routen vom Lager zum Krankenhaus aus:

wenigste Straßen: Lager → Stadion → Krankenhaus (2 Straßen, 18 Min.)
am schnellsten: Lager → Markt → Platz → Kino → Krankenhaus (4 Straßen, 13 Min.)

Weitere Aufgaben

Nur die Minuten. Schreibe eine Variante von fastest, die die Minuten bis zu jeder Kreuzung zurückgibt, ohne am Ziel anzuhalten. Welche Kreuzung ist am weitesten vom Lager entfernt?
Ohne Kreuzung. Der Platz ist wegen einer Veranstaltung gesperrt. Wie lässt du ihn weg, ohne die Karte anzufassen?
Eine leere Ringstraße. Nachts ist die Ringstraße leer und dauert 6 Min. Ändere die Minuten in der Karte: Welche Route ist jetzt die schnellste, und ist es dieselbe wie die von BFS?

Test

Teste dich

1. BFS und Dijkstra geben vom Lager zum Krankenhaus verschiedene Routen. Welche ist falsch?BFS, weil es langsamer istKeine: BFS antwortet auf „wenigste Straßen“, Dijkstra auf „wenigste Minuten“Dijkstra, weil es mehr Straßen nimmt

2. Warum findet BFS in dieser Stadt nicht die schnellste Route?Weil die Warteschlange FIFO istWeil es eine Einbahnstraße gibtDie Straßen dauern verschieden viele Minuten, und BFS zählt jede Straße als eine

3. Bei Dijkstra hat der Eintrag, der aus der Warteschlange kommt, manchmal mehr Minuten als dist. Was macht das Programm?Es aktualisiert dist mit der größeren ZahlEs hält anEs überspringt ihn: Die Kreuzung ist schon mit weniger Minuten herausgekommen

Sinken die Minuten bis zu einer Kreuzung, legt das Programm einen neuen Eintrag an, und der alte bleibt in der Warteschlange. Kommt der alte heraus, ist er veraltet: minutes > dist[at], und er wird übersprungen.

4. Markt -> Park ist eine Einbahnstraße. Was gehört in die Adjazenzliste?Park bei den Nachbarn des Markts, aber nicht Markt bei den Nachbarn des ParksBeidesNur Markt bei den Nachbarn des Parks

5. Die Stadt ist ein Raster mit n Kreuzungen. Wie wächst die Zahl der Operationen der beiden Algorithmen?Beide O(n²)BFS O(n), Dijkstra O(n log n): Der Heap fügt pro Straße log n hinzuBeide O(n)

Navigation in der Stadt

Cookies