Dijkstra's Algorithmus

Dijkstras Algorithmus ist ein Verfahren zur Bestimmung der kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen mit nicht-negativen Kantenkosten. Er arbeitet, indem er schrittweise die günstigsten Pfade ausgehend vom Startknoten erweitert und dabei die bisher kürzesten bekannten Distanzen aktualisiert.

Funktionsweise

  1. Initialisierung: Weise allen Knoten die beiden Eigenschaften „Distanz“ und „Vorgänger“ zu. (Wir bilden den Vorgängerknoten direkt im Suchbaum ab, und fügen die Distanz als Information im Knoten hinzu.) Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit "unendlich".
  2. Solange es noch unbesuchte Knoten gibt, tue folgendes:
    1. Knoten auswählen: Wähle darunter denjenigen mit minimaler (aufsummierter) Distanz aus.
    2. Speichern: Speichere, dass dieser Knoten schon besucht wurde.
    3. Berechnen: Berechne für alle noch unbesuchten Nachbarknoten die Gesamtdistanz des Pfades über die Summe des jeweiligen Kantengewichtes und der bereits berechneten Distanz des Pfades vom Startknoten zum aktuellen Knoten.
    4. Update: Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte bisherige aufsummierte Distanz des Pfades, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.

Beispiel 1 - Dijkstra

  1. Wir initialisieren unser Suchproblem.
  2. Wir wählen als nächstes den Knoten mit der geringsten Entfernung (0), Knoten S. Wir speichern, dass wir S besucht haben und berechnen dann für alle Nachbarn die Gesamtdistanz. Vom Startknoten aus entspricht die Gesamtdistanz eifach den Kosten der Kanten zum jeweiligen Zustand. Wir fügen dann diese Werte den Nachbarn von S: B und C hinzu.
  3. Wir wählen als nächstes den unbesuchten Knoten mit der geringsten Entfernung (3), Knoten B. Wir speichern, dass wir B besucht haben (Besucht: S, B) und berechnen dann für alle Nachbarn die Gesamtdistanz. Wir fügen dann diese Werte den Nachbarn von B: A und D hinzu.
  4. Wir wählen wieder den Knoten mit der geringsten Entfernung (4), Knoten C. Wir speichern, dass wir C besucht haben (Besucht: S, B, C) und berechnen dann für alle Nachbarn die Gesamtdistanz. Wir fügen dann diese Werte den Nachbarn von B: A hinzu, weil der neu berechnete Wert kleiner ist, als der Wert der bereits bei A steht. Wir haben herausgefunden, dass wir schneller über C nach A gelangen können als über B.
  5. Wir wählen wieder den Knoten mit der geringsten Entfernung (6), Knoten A oder D. Wir nehmen A, weil er zuerst im Alphabet vorkommt. Wir speichern, dass wir A besucht haben (Besucht: S, B, C, A) und berechnen dann für alle Nachbarn die Gesamtdistanz. Wir fügen dann diese Werte den Nachbarn von A: G hinzu, weil da noch kein Wert steht. Wir haben nun einen Weg vom Start zum Ziel gefunden.
  6. Wir wählen wieder den Knoten mit der geringsten Entfernung (6), D. Wir speichern, dass wir D besucht haben (Besucht: S, B, C, D). Jetzt haben wir alle Knoten besucht. Wir berechnen dann für alle Nachbarn die Gesamtdistanz. Wir fügen dann diese Werte den Nachbarn von D: G hinzu, weil der neu berechnete Wert kleiner ist, als der Wert der bereits bei G steht. Wir haben nun einen kürzeren Weg vom Start zum Ziel gefunden.

Der Suchbaum zeigt uns nun den schnellsten Weg vom Startknoten zu jedem anderen Knoten im Graphen.

Beispiel 2

Übungen 2

  1. Schreiben Sie diese Beispiel auf Papier ab und finden Sie den schnellsten Weg vom Startknoten zum Zielknoten mit Dijkstra's Algorithmus.
  2. Versuchen Sie zu erklären, was eigentlich der Unterschied zwischen Dijkstra's Algorithmus und der Breitensuche ist. Sind die Voraussetzungen gleich?

Beispiel 3

Übungen 3

  1. Der schnellste Weg zum Ziel ist hier offensichtlich. Doch was passiert, wenn Sie hier Dijstra's Algorithmus anwenden? Sehen Sie ein Problem?
Zurück zum Menu

Graph