====== Dijkstras Algorithmus ====== ===== Überblick ===== **Dijkstras Algorithmus** berechnet die kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen. Er eignet sich für Graphen, deren Kantengewichte nicht negativ sind. Der Algorithmus wurde vom niederländischen Informatiker Edsger W. Dijkstra entwickelt und gehört zu den grundlegenden Verfahren der Graphentheorie. Typische Einsatzgebiete sind: * Routenplanung * Netzwerkprotokolle * Verkehrsanalysen * Logistik * Wegfindung in Computerspielen ===== Voraussetzungen ===== Ein Graph besteht aus: * **Knoten**, die beispielsweise Orte, Geräte oder Zustände darstellen * **Kanten**, die zwei Knoten miteinander verbinden * **Kantengewichten**, die etwa Entfernungen, Kosten oder Übertragungszeiten beschreiben Dijkstras Algorithmus kann auf gerichtete und ungerichtete Graphen angewendet werden. Sämtliche Kantengewichte müssen jedoch größer oder gleich null sein: Gewicht ≥ 0 ===== Grundidee ===== Der Algorithmus verwaltet für jeden Knoten eine vorläufige Distanz zum Startknoten. Zu Beginn ist nur die Distanz des Startknotens bekannt. Sie beträgt ''0''. Die Distanzen aller anderen Knoten werden zunächst als unendlich betrachtet. Anschließend wird wiederholt der noch nicht abschließend bearbeitete Knoten mit der kleinsten bekannten Distanz ausgewählt. Von diesem Knoten aus prüft der Algorithmus, ob sich die Distanzen zu seinen Nachbarn verbessern lassen. Dieser Vorgang wird als **Relaxierung** bezeichnet. ===== Ablauf ===== * Setze die Distanz des Startknotens auf ''0''. * Setze die Distanz aller anderen Knoten auf unendlich. * Füge den Startknoten in eine Prioritätswarteschlange ein. * Entnimm den Knoten mit der kleinsten bekannten Distanz. * Prüfe für jede ausgehende Kante, ob der Weg über den aktuellen Knoten kürzer ist. * Aktualisiere gegebenenfalls die Distanz und den Vorgängerknoten. * Wiederhole den Vorgang, bis keine erreichbaren Knoten mehr vorhanden sind. Soll nur der kürzeste Weg zu einem bestimmten Ziel berechnet werden, kann der Algorithmus beendet werden, sobald der Zielknoten aus der Prioritätswarteschlange entnommen wird. ===== Relaxierung einer Kante ===== Angenommen, der Algorithmus betrachtet eine Kante vom Knoten ''u'' zum Knoten ''v''. Das Kantengewicht wird mit ''w(u, v)'' bezeichnet. Die bisher bekannte Distanz zu ''v'' wird aktualisiert, wenn folgende Bedingung erfüllt ist: distanz[u] + w(u, v) < distanz[v] In diesem Fall gilt: distanz[v] = distanz[u] + w(u, v) vorgaenger[v] = u Der gespeicherte Vorgängerknoten ermöglicht es, nach Abschluss des Algorithmus nicht nur die Länge, sondern auch den konkreten Verlauf des kürzesten Weges zu rekonstruieren. ===== Pseudocode ===== funktion dijkstra(graph, start): distanz = leere Zuordnung vorgaenger = leere Zuordnung warteschlange = leere Prioritaetswarteschlange ``` fuer jeden knoten im graph: distanz[knoten] = unendlich vorgaenger[knoten] = nicht definiert distanz[start] = 0 warteschlange.einfuegen(start, prioritaet=0) solange warteschlange nicht leer ist: u = warteschlange.entferne_minimum() fuer jede kante von u nach v: neue_distanz = distanz[u] + gewicht(u, v) wenn neue_distanz < distanz[v]: distanz[v] = neue_distanz vorgaenger[v] = u warteschlange.einfuegen_oder_aktualisieren( v, prioritaet=neue_distanz ) zurueckgeben distanz, vorgaenger ``` ===== Beispiel ===== Gegeben sei ein gerichteter Graph mit folgenden gewichteten Kanten: A → B: 4 A → C: 1 C → B: 2 B → D: 1 C → D: 5 Gesucht werden die kürzesten Wege vom Startknoten ''A''. ==== Initialisierung ==== ^ Knoten ^ Vorläufige Distanz ^ | A | 0 | | B | ∞ | | C | ∞ | | D | ∞ | ==== Verarbeitung von A ==== Von ''A'' aus werden die Knoten ''B'' und ''C'' erreicht. ^ Knoten ^ Vorläufige Distanz ^ | A | 0 | | B | 4 | | C | 1 | | D | ∞ | Der noch nicht verarbeitete Knoten mit der kleinsten vorläufigen Distanz ist ''C''. ==== Verarbeitung von C ==== Über ''C'' kann ''B'' mit den Gesamtkosten 1 + 2 = 3 erreicht werden. Dieser Weg ist kürzer als der bisher bekannte direkte Weg von ''A'' nach ''B'' mit den Kosten ''4''. Auch ''D'' wird über ''C'' mit den Kosten 1 + 5 = 6 erreicht. ^ Knoten ^ Vorläufige Distanz ^ | A | 0 | | B | 3 | | C | 1 | | D | 6 | ==== Verarbeitung von B ==== Über ''B'' kann ''D'' mit den Gesamtkosten 3 + 1 = 4 erreicht werden. Dieser Weg verbessert die bisher bekannte Distanz von ''6''. ==== Ergebnis ==== ^ Knoten ^ Kürzeste Distanz von A ^ | A | 0 | | C | 1 | | B | 3 | | D | 4 | Der kürzeste Weg von ''A'' nach ''D'' lautet: A → C → B → D Die Gesamtkosten betragen: 4 ===== Implementierung in Python ===== Der Graph wird als Zuordnung dargestellt. Jedem Knoten ist eine Liste aus Nachbarknoten und Kantengewichten zugeordnet. import heapq from collections.abc import Hashable, Mapping, Sequence from math import inf from typing import TypeVar Node = TypeVar("Node", bound=Hashable) def dijkstra( graph: Mapping[Node, Sequence[tuple[Node, float]]], start: Node, ) -> tuple[dict[Node, float], dict[Node, Node | None]]: """ Berechnet die kürzesten Distanzen vom Startknoten zu allen erreichbaren Knoten. ``` Der Graph wird folgendermaßen dargestellt: knoten -> [(nachbar, gewicht), ...] Alle Kantengewichte müssen nicht negativ sein. """ if start not in graph: raise KeyError( f"Startknoten {start!r} ist nicht im Graphen enthalten." ) distances: dict[Node, float] = { node: inf for node in graph } predecessors: dict[Node, Node | None] = { node: None for node in graph } distances[start] = 0 queue: list[tuple[float, Node]] = [(0, start)] while queue: current_distance, current_node = heapq.heappop(queue) # Veraltete Einträge überspringen. if current_distance > distances[current_node]: continue for neighbor, weight in graph[current_node]: if weight < 0: raise ValueError( "Dijkstras Algorithmus unterstützt " "keine negativen Kantengewichte." ) if neighbor not in distances: raise KeyError( f"Nachbarknoten {neighbor!r} fehlt im Graphen." ) new_distance = current_distance + weight if new_distance < distances[neighbor]: distances[neighbor] = new_distance predecessors[neighbor] = current_node heapq.heappush( queue, (new_distance, neighbor), ) return distances, predecessors ``` ==== Beispielaufruf ==== graph = { "A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": [], } distances, predecessors = dijkstra(graph, "A") print(distances) Ausgabe: {'A': 0, 'B': 3, 'C': 1, 'D': 4} ===== Rekonstruktion eines Weges ===== Mithilfe der Vorgängerknoten kann der konkrete Weg vom Startknoten zum Zielknoten rekonstruiert werden. from collections.abc import Hashable, Mapping from typing import TypeVar Node = TypeVar("Node", bound=Hashable) def reconstruct_path( predecessors: Mapping[Node, Node | None], start: Node, target: Node, ) -> list[Node]: """ Rekonstruiert den Weg vom Startknoten zum Zielknoten. """ if start not in predecessors: raise KeyError("Der Startknoten ist nicht bekannt.") ``` if target not in predecessors: raise KeyError("Der Zielknoten ist nicht bekannt.") path: list[Node] = [] current: Node | None = target while current is not None: path.append(current) if current == start: path.reverse() return path current = predecessors[current] # Der Zielknoten ist vom Startknoten aus # nicht erreichbar. return [] ``` Beispiel: path = reconstruct_path( predecessors, start="A", target="D", ) print(path) Ausgabe: ['A', 'C', 'B', 'D'] ===== Laufzeitkomplexität ===== Die Laufzeit hängt von der verwendeten Datenstruktur ab. ==== Einfache Implementierung ==== Bei einer einfachen Implementierung mit einem Array oder einer linearen Suche nach dem nächsten Knoten beträgt die Laufzeit: O(V²) Dabei bezeichnet ''V'' die Anzahl der Knoten. ==== Implementierung mit Prioritätswarteschlange ==== Bei Verwendung einer Adjazenzliste und einer binären Prioritätswarteschlange beträgt die Laufzeit: O((V + E) · log V) Häufig wird die Laufzeit vereinfacht als O(E · log V) angegeben. Dabei bezeichnet: * ''V'' die Anzahl der Knoten * ''E'' die Anzahl der Kanten Für dünn besetzte Graphen mit vergleichsweise wenigen Kanten ist die Variante mit Prioritätswarteschlange meist deutlich effizienter. ===== Speicherkomplexität ===== Der Algorithmus benötigt Speicher für: * die Darstellung des Graphen * die bekannten Distanzen * die Vorgängerknoten * die Prioritätswarteschlange Bei einer Darstellung des Graphen als Adjazenzliste beträgt der Speicherbedarf typischerweise: O(V + E) ===== Korrektheit ===== Sobald ein Knoten mit der kleinsten bekannten Distanz aus der Prioritätswarteschlange entnommen wird, ist seine Distanz endgültig. Ein später entdeckter Weg kann nicht kürzer sein, da sämtliche Kantengewichte nicht negativ sind. Genau diese Eigenschaft ist der Grund dafür, dass Dijkstras Algorithmus bei negativen Kantengewichten nicht zuverlässig funktioniert. Eine negative Kante könnte einen bereits abgeschlossenen Weg nachträglich verbessern. ===== Einschränkungen ===== ==== Negative Kantengewichte ==== Dijkstras Algorithmus darf nicht für Graphen mit negativen Kantengewichten verwendet werden. Für solche Graphen eignet sich beispielsweise der [[bellman_ford_algorithmus|Bellman-Ford-Algorithmus]]. Dieser kann negative Kantengewichte verarbeiten und negative Zyklen erkennen, ist jedoch in der Regel langsamer. ==== Negative Zyklen ==== Enthält ein Graph einen erreichbaren Zyklus mit negativem Gesamtgewicht, existiert kein eindeutig kürzester Weg. Die Wegkosten könnten durch wiederholtes Durchlaufen des Zyklus beliebig weit reduziert werden. Dijkstras Algorithmus kann solche Situationen nicht korrekt erkennen oder behandeln. ==== Große Graphen ==== Bei sehr großen Graphen können sowohl die Speicherung des Graphen als auch die Prioritätswarteschlange erheblichen Speicher beanspruchen. In solchen Fällen werden häufig spezialisierte Datenstrukturen oder optimierte Varianten des Algorithmus verwendet. ===== Typische Anwendungsbereiche ===== Dijkstras Algorithmus wird unter anderem eingesetzt für: * die Berechnung kürzester Straßenverbindungen * die Berechnung von Schienenverbindungen * die Weiterleitung von Datenpaketen in Netzwerken * die Wegfindung in Spielen und Simulationen * die Planung logistischer Prozesse * die Analyse sozialer Netzwerke * die Analyse technischer Netzwerke * die Berechnung minimaler Kosten in Zustandsräumen In realen Navigationssystemen werden häufig optimierte oder spezialisierte Verfahren verwendet. Dazu gehören beispielsweise: * [[a_stern_algorithmus|A*-Algorithmus]] * bidirektionale Suchverfahren * hierarchische Routenplanungsverfahren ===== Abgrenzung zum A*-Algorithmus ===== Dijkstras Algorithmus sucht gleichmäßig in alle relevanten Richtungen und verwendet ausschließlich die bisher entstandenen Wegkosten. Der [[a_stern_algorithmus|A*-Algorithmus]] ergänzt diese Kosten um eine Heuristik, die die verbleibende Entfernung zum Ziel schätzt. Mit einer geeigneten Heuristik kann A* deutlich weniger Knoten untersuchen. Wird die Heuristik für alle Knoten auf ''0'' gesetzt, verhält sich A* wie Dijkstras Algorithmus. ^ Eigenschaft ^ Dijkstra ^ A* ^ | Verwendet bisherige Wegkosten | Ja | Ja | | Verwendet eine Heuristik | Nein | Ja | | Berechnet Wege zu allen Knoten | Typischerweise ja | Typischerweise nein | | Zielgerichtete Suche | Nein | Ja | | Erfordert nicht negative Kantengewichte | Ja | Ja | ===== Häufige Implementierungsfehler ===== ==== Negative Kantengewichte verwenden ==== Die Anwendung auf Graphen mit negativen Kanten kann falsche Ergebnisse liefern. Vor dem Start des Algorithmus sollte daher geprüft werden, ob sämtliche Kantengewichte nicht negativ sind. ==== Veraltete Einträge nicht überspringen ==== Viele Prioritätswarteschlangen unterstützen keine direkte Verringerung einer Priorität. Wird eine kürzere Distanz gefunden, wird deshalb häufig ein neuer Eintrag in die Warteschlange eingefügt. Der ältere Eintrag bleibt zunächst erhalten. Beim Entnehmen muss geprüft werden, ob der Eintrag noch aktuell ist: if current_distance > distances[current_node]: continue ==== Falsche Abbruchbedingung ==== Ein Zielknoten darf nicht bereits beim ersten Entdecken als abgeschlossen betrachtet werden. Der kürzeste Weg steht erst fest, wenn der Zielknoten als Knoten mit der aktuell kleinsten Distanz aus der Prioritätswarteschlange entnommen wird. ==== Unvollständige Graphdarstellung ==== Auch Knoten ohne ausgehende Kanten sollten in der Datenstruktur vorhanden sein. Beispiel: graph = { "A": [("B", 1)], "B": [], } ==== Vorgängerknoten nicht speichern ==== Werden nur die Distanzen gespeichert, kann zwar die Länge eines kürzesten Weges bestimmt werden, nicht jedoch dessen konkreter Verlauf. Für die Wegrekonstruktion muss bei jeder Verbesserung auch der Vorgängerknoten gespeichert werden. ===== Varianten ===== ==== Abbruch an einem Zielknoten ==== Wird nur der kürzeste Weg zu einem bestimmten Ziel gesucht, kann der Algorithmus beendet werden, sobald der Zielknoten aus der Prioritätswarteschlange entnommen wurde. if current_node == target: break ==== Mehrere Startknoten ==== Bei einer Mehrquellensuche werden mehrere Startknoten mit der Anfangsdistanz ''0'' in die Prioritätswarteschlange eingefügt. Der Algorithmus berechnet anschließend für jeden Knoten die kürzeste Entfernung zu einem der Startknoten. ==== Bidirektionale Suche ==== Bei einer bidirektionalen Variante wird gleichzeitig vom Startknoten und vom Zielknoten aus gesucht. Sobald sich beide Suchbereiche treffen, kann der vollständige Weg zusammengesetzt werden. Diese Variante kann insbesondere bei großen Graphen deutlich weniger Knoten untersuchen. ===== Zusammenfassung ===== Dijkstras Algorithmus ist ein effizientes und weit verbreitetes Verfahren zur Berechnung kürzester Wege in gewichteten Graphen. Er arbeitet, indem er stets den noch nicht abgeschlossenen Knoten mit der kleinsten bekannten Entfernung auswählt und anschließend dessen Kanten relaxiert. Die wichtigsten Eigenschaften sind: * Der Algorithmus berechnet kürzeste Wege von einem Startknoten zu allen erreichbaren Knoten. * Er unterstützt gerichtete und ungerichtete Graphen. * Er setzt nicht negative Kantengewichte voraus. * Mit einer Prioritätswarteschlange ist er für dünn besetzte Graphen besonders effizient. * Mithilfe von Vorgängerknoten können konkrete Wege rekonstruiert werden. * Für Graphen mit negativen Kantengewichten muss ein anderes Verfahren verwendet werden. Aufgrund seiner einfachen Grundidee und seiner praktischen Bedeutung gehört Dijkstras Algorithmus zu den wichtigsten Standardalgorithmen der Informatik. ===== Siehe auch ===== * [[graphentheorie|Graphentheorie]] * [[kuerzeste_wege|Kürzeste Wege]] * [[a_stern_algorithmus|A*-Algorithmus]] * [[bellman_ford_algorithmus|Bellman-Ford-Algorithmus]] * [[breitensuche|Breitensuche]] * [[prioritaetswarteschlange|Prioritätswarteschlange]] =====Links===== * [[https://www.youtube.com/watch?v=n1VUnHD62r0|FreeCodeCamp | Youtube]]