Dijkstras Algorithmus

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

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

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.

* 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.

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.

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
```

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.

Von A aus werden die Knoten B und C erreicht.

Der noch nicht verarbeitete Knoten mit der kleinsten vorläufigen Distanz ist 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.

Über B kann D mit den Gesamtkosten

3 + 1 = 4

erreicht werden. Dieser Weg verbessert die bisher bekannte Distanz von 6.

Der kürzeste Weg von A nach D lautet:

A → C → B → D

Die Gesamtkosten betragen:

4

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
```

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}

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']

Die Laufzeit hängt von der verwendeten Datenstruktur ab.

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.

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.

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)

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.

Dijkstras Algorithmus darf nicht für Graphen mit negativen Kantengewichten verwendet werden.

Für solche Graphen eignet sich beispielsweise der Bellman-Ford-Algorithmus. Dieser kann negative Kantengewichte verarbeiten und negative Zyklen erkennen, ist jedoch in der Regel langsamer.

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.

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.

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*-Algorithmus * bidirektionale Suchverfahren * hierarchische Routenplanungsverfahren

Dijkstras Algorithmus sucht gleichmäßig in alle relevanten Richtungen und verwendet ausschließlich die bisher entstandenen Wegkosten.

Der 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.

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.

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

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.

Auch Knoten ohne ausgehende Kanten sollten in der Datenstruktur vorhanden sein.

Beispiel:

graph = {
    "A": [("B", 1)],
    "B": [],
}

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.

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

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.

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.

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.

* Graphentheorie * Kürzeste Wege * A*-Algorithmus * Bellman-Ford-Algorithmus * Breitensuche * Prioritätswarteschlange

• FreeCodeCamp | Youtube