Notizen

Dijkstra-Algorithmus

tagsgraphentheorie

Der Dijkstra-Algorithmus ist ein Algorithmus zur Berechnung kürzester Wege von einem Knoten zu allen anderen Knoten in gewichteten Graphen mit nicht negativen Kantengewichten.

Idee

Die Idee basiert auf der des Prim-Algorithmus, mit dem Unterschied, dass nicht einzelne Kantengewichte betrachtet werden, sondern Summen von Kantengewichten. Wie auch der Bellmann-Ford-Algorithmus arbeitet er mittels Relaxation.

  • Alle Knoten werden nach ihrer bisher identifizierten Distanz zum Startknoten aufsteigend sortiert
  • Gestartet wird beim Quellknoten, dieser hat die Distanz 0. Alle anderen Knoten haben die Distanz
  • Schritt für Schritt wird der Knoten mit der aktuell kleinsten Distanz herausgenommen und geprüft, ob Kanten, die an diesem Knoten starten, Distanzen zu anderen Knoten kleiner machen (Relaxation)

Begründung zur Einschränkung

Der Algorithmus funktioniert nur, wenn es keine negativen Kantengewichte gibt. Das liegt daran, dass der Algorithmus Knoten frühzeitig entfernt und nachdem er sie abgearbeitet hat, nicht mehr zu ihnen zurück kommt. Das macht er, weil er davon ausgeht, dass er davon ausgeht, dass wenn der Knoten herausgenommen wurde, er bereits billigst erreicht wurde. Würden negative Gewichte zugelassen, könnten diese ja später auftauchen und einen billigeren Pfad möglich machen. Diese würde aber dann nicht mehr berücksichtigt, weil wir ja nicht mehr zum Knoten zurück kommen.

Implementierung

Zum speichern der nach Distanz aufsteigend sortierten Knoten eignet sich ein Min-Heap.

Pseudocode

Seien ein gerichteter Graph, eine positive Gewichtung, d.h. , und eine Quelle.

  • Algorithmus Dijkstra(G, w, s):
    • Für jeden Knoten :
      • .dist =
      • .pred = NULL
    • .dist = 0
    • = BuildHeap() Min-Heap über Distanzen
    • Solange nicht leer:
      • = .extractMin() Knoten mit kleinster Distanz
      • Für jeden Knoten AdjList[]:
        • Falls .dist > .dist + Ggf. relaxieren
          • .dist = .dist +
          • .pred =
          • .decreaseKey(, .dist)

Laufzeit

  • Initialisierung:
  • BuildHeap:
  • Solange Heap nicht leer:
  • ExtractMin:
  • Für jeden Knoten aus AdjListe:
  • DecreaseKey:

Insgesamt ergibt sich eine Gesamtlaufzeit von:

Backlinks