BWL-Lexikon.de
  • Home
  • Grundlagen
    • Aufbau eines Betriebs
    • Definitionen
    • Organisation
    • Personalwirtschaft
    • Planung und Entscheidung
    • Produktionsfaktoren
    • Unternehmensführung
  • BWL
    • Rechtsformen
    • Rechnungswesen
      • Finanzbuchhaltung
      • Kostenarten
      • Jahresabschluss
    • Marketing
    • Logistik
      • Logistik Kennzahlen
      • Beschaffung
      • Lagerverfahren
      • Materialarten
    • Kennzahlen
      • Bilanzkennzahlen
      • Produktivitätskennzahlen
      • Rentabilitätskennzahlen
      • Kennzahlen der GuV
  • VWL
    • Makroökonomie
    • Mikroökonomie
  • Fehler gefunden?

Du bist hier: Startseite » Alle Lektionen » Aufbau eines Betriebs » Planung und Entscheidung » Operations Research » Dijkstra Algorithmus

Dijkstra Algorithmus

Enthält: Beispiele · Definition · Grafiken · Übungsfragen

Der Dijkstra Algorithmus gehört zur Gruppe der Greedy Algorithmen. Er dient der Berechnung des kürzesten Pfades in einem Graphen von einem gegebenen Startpunkt aus.

Dieses Kapitel zeigt dir, warum der Dijkstra Algorithmus wichtig ist und was man unter ihm versteht. Außerdem zeigen wir dir, wie du den Dijkstra Algorithmus anwendest und stellen dir am Ende einige Übungsaufgaben zur Verfügung, die dich bei der Prüfungsvorbereitung unterstützen können.

Inhalt dieser Lektion

  • Warum ist der Dijkstra Algorithmus wichtig?
  • Was versteht man unter dem Dijkstra Algorithmus?
    • Beispiel: Anwendung des Dijkstra Algorithmus
      • 2. Schritt: 1. Iteration
      • 3. Schritt: 2. Iteration
      • 4. Schritt: 3. Iteration
      • 5. Schritt: 4. Iteration
      • 6. Schritt: 5. Iteration
  • Übungsfragen

Warum ist der Dijkstra Algorithmus wichtig?

Zur Lösung von Optimierungsproblemen im Rahmen des Operations Research im Betrieb werden häufig Algorithmen verwendet. Einer von ihnen ist der „Dijkstra Algorithmus“, welcher zur Gruppe der Greedy Algorithmen gehört.

Mithilfe dieses Algorithmus ist es möglich, den kostengünstigsten bzw. kürzesten Weg in einem Graphen zu berechnen. Dazu werden die Kantengewichte des Graphen betrachtet, welche die Kosten für den Weg von einem Knoten zum nächsten beschreiben. Der Dijkstra Algorithmus wird beispielsweise in Routenplanern und Navigationsgeräten eingesetzt

Was versteht man unter dem Dijkstra Algorithmus?

Der nach seinem Erfinder Edsger W. Dijkstra benannte Dijkstra Algorithmus ist eine Methode zur Lösung von Optimierungsproblemen, bei denen nach dem kostengünstigsten oder kürzesten Pfad in einem Graphen gesucht wird.

Grundvoraussetzung zur Anwendung des Dijkstra Algorithmus ist, dass die Kantengewichte innerhalb des zu untersuchenden Graphen nicht negativ sind. Sind negative Kantengewichte vorhanden, eignet sich der „Bellman-Ford-Algorithmus“ besser zur Lösung des Problems.

Beispiel: Anwendung des Dijkstra Algorithmus

Beispiel
Die „Schokofanten AG“ hat ein neues Produkt entwickelt, um ihre Marktposition weiter auszubauen. Um das Produkt erfolgreich am Markt einzuführen und dem Fachpublikum vorzustellen, möchte der Geschäftsführer persönlich zur wichtigsten Schokoladenmesse des Landes in die Stadt E reisen.

Um seine Reiseroute zu planen, stellt er folgenden Graph auf, der die möglichen Reisewege und die Entfernungen der einzelnen Knotenpunkte zueinander darstellt:

Dijkstra Algorithmus - Anwendungsbeispiel
Dijkstra Algorithmus – Anwendungsbeispiel

Damit die kürzeste Route von Stadt A nach Stadt E gefunden werden kann, wird nun der Dijkstra Algorithmus angewendet:

1. Schritt: Initialisierung des Algorithmus

Um den Algorithmus zu initialisieren, wird eine Tabelle angelegt. Zu Beginn betragen die Kosten Null, da am Startpunkt begonnen wird. Der Weg zu den weiteren Knoten ist noch nicht bekannt, daher nehmen wir für die Kosten vorerst „unendlich“ an.

In der Warteschlange befinden sich alle Knoten, die wir bereits gefunden haben. Zu Beginn ist das lediglich der Startpunkt A. Einen Vorgänger des Startpunktes gibt es nicht. Die gefüllte Tabelle sieht dann also folgendermaßen aus:

Iteration ABCDE 
0Kosten:

Vorgänger:
0

-
∞

-
∞

-
∞

-
∞

-
Warteschlange: A
Erledigt: -
Ausgewählt: A
Nachfolger: B, D
1
2
3
4
5

2. Schritt: 1. Iteration

Nach der Initialisierung des Algorithmus kann mit der ersten Iteration begonnen werden. In der Warteschlange aus dem vorherigen Schritt befindet sich der Knoten A. Daher wird dieser nun ausgewählt. Betrachtet werden dessen direkte Nachfolger, die Knoten B und D.

Die Entfernung von A nach B beträgt 100, die von A nach D 50. Diese stellen die Kosten dar. Da die beiden Nachfolger des Startpunktes nun betrachtet wurden, gilt dieser als erledigt. In der Warteschlange stehen nun B und D.

Mögliche Nachfolger der betrachteten Knoten sind C und E. Die Tabelle sieht dementsprechend folgendermaßen aus:

Iteration ABCDE 
0Kosten:

Vorgänger:
0

-
∞

-
∞

-
∞

-
∞

-
Warteschlange: A
Erledigt: -
Ausgewählt: A
Nachfolger: B, D
1Kosten:

Vorgänger:
0

-
100

A
∞

-
50

A
∞

-
Warteschlange: B,D
Erledigt: A
Ausgewählt: B, D
Nachfolger: C,E
2
3
4
5

3. Schritt: 2. Iteration

Es folgt nun die 2. Iteration. Hierzu wird der Knoten aus der Warteschlange ausgewählt, welcher die geringsten Kosten aufweist, also Knoten D. Der Nachfolger dieses Knotens, Knoten E, wird nun betrachtet.

Die Kosten, um zum Knoten E zu gelangen, betragen 300. Da Knoten D nun betrachtet wurde, kann dieser aus der Warteschlange genommen und als erledigt markiert werden. Knoten B bleibt in der Warteschlange und wird um Knoten E ergänzt.

Die Tabelle gestaltet sich dann folgendermaßen:

Iteration ABCDE 
0Kosten:

Vorgänger:
0

-
∞

-
∞

-
∞

-
∞

-
Warteschlange: A
Erledigt: -
Ausgewählt: A
Nachfolger: B, D
1Kosten:

Vorgänger:
0

-
100

A
∞

-
50

A
∞

-
Warteschlange: B,D
Erledigt: A
Ausgewählt: B, D
Nachfolger: C,E
2Kosten:

Vorgänger:
0

-
100

A
50

A
∞

-
300

D
Warteschlange: B,E
Erledigt: A, D
Ausgewählt: D
Nachfolger: C,E
3
4
5

4. Schritt: 3. Iteration

Auch bei der dritten Iteration wird nach dem gleichen Schema vorgegangen. Wir schauen uns nun die Kosten für den Knoten C an. Diese betragen 200. Sein direkter Vorgänger ist Knoten B. Wir können B damit als erledigt markieren und C zusätzlich in die Warteschlange aufnehmen.

Diese Informationen werden in der Tabelle ergänzt:

Iteration ABCDE 
0Kosten:

Vorgänger:
0

-
∞

-
∞

-
∞

-
∞

-
Warteschlange: A
Erledigt: -
Ausgewählt: A
Nachfolger: B, D
1Kosten:

Vorgänger:
0

-
100

A
∞

-
50

A
∞

-
Warteschlange: B,D
Erledigt: A
Ausgewählt: B, D
Nachfolger: C,E
2Kosten:

Vorgänger:
0

-
100

A
50

A
∞

-
300

D
Warteschlange: B,E
Erledigt: A, D
Ausgewählt: D
Nachfolger: C,E
3Kosten:

Vorgänger:
0

-
100

A
200

B
50

A
300

D
Warteschlange: C,E
Erledigt: A, D, B
Ausgewählt: C
Nachfolger: E
4
5

5. Schritt: 4. Iteration

Betrachten wir nun den Nachfolger von Knoten C. Dies ist Knoten E. Aktuell betragen die Kosten für E 300. Wenn wir aber den Weg über Knoten B und C wählen, betragen die neuen Kosten für E nur noch 250 mit dem neuen Vorgänger C. Damit ist auch Knoten E erledigt. Es gibt keine weiteren Nachfolger.

Iteration ABCDE 
0Kosten:

Vorgänger:
0

-
∞

-
∞

-
∞

-
∞

-
Warteschlange: A
Erledigt: -
Ausgewählt: A
Nachfolger: B, D
1Kosten:

Vorgänger:
0

-
100

A
∞

-
50

A
∞

-
Warteschlange: B,D
Erledigt: A
Ausgewählt: B, D
Nachfolger: C,E
2Kosten:

Vorgänger:
0

-
100

A
50

A
∞

-
300

D
Warteschlange: B,E
Erledigt: A, D
Ausgewählt: D
Nachfolger: C,E
3Kosten:

Vorgänger:
0

-
100

A
200

B
50

A
300

D
Warteschlange: C,E
Erledigt: A, D, B
Ausgewählt: C
Nachfolger: E
4Kosten:

Vorgänger:
0

-
100

A
200

B
50

A
250

C
Warteschlange: E
Erledigt: A, B, C, D
Ausgewählt: E
Nachfolger: -
5

6. Schritt: 5. Iteration

In der letzten Iteration stellen wir fest, dass alle Knoten erledigt sind, da wir keinen Knoten mehr in die Warteschlange aufnehmen können. Wir können unseren Algorithmus an dieser Stelle also beenden.

Iteration ABCDE 
0Kosten:

Vorgänger:
0

-
∞

-
∞

-
∞

-
∞

-
Warteschlange: A
Erledigt: -
Ausgewählt: A
Nachfolger: B, D
1Kosten:

Vorgänger:
0

-
100

A
∞

-
50

A
∞

-
Warteschlange: B,D
Erledigt: A
Ausgewählt: B, D
Nachfolger: C,E
2Kosten:

Vorgänger:
0

-
100

A
50

A
∞

-
300

D
Warteschlange: B,E
Erledigt: A, D
Ausgewählt: D
Nachfolger: C,E
3Kosten:

Vorgänger:
0

-
100

A
200

B
50

A
300

D
Warteschlange: C,E
Erledigt: A, D, B
Ausgewählt: C
Nachfolger: E
4Kosten:

Vorgänger:
0

-
100

A
200

B
50

A
250

C
Warteschlange: E
Erledigt: A, B, C, D
Ausgewählt: E
Nachfolger: -
5Kosten:

Vorgänger:
0

-
100

A
200

B
50

A
250

C
Warteschlange: -
Erledigt: A, B, C, D, E
Ausgewählt: -
Nachfolger: -

Anhand der vollständigen Tabelle können wir nun den günstigsten Weg vom Startpunkt A zum Endpunkt E ablesen. Dazu betrachten wir die Tabelle rekursiv. Das bedeutet, wir starten die Betrachtung beim Knoten E. Dieser hat Gesamtkosten von 250. Sein Vorgänger ist Knoten C. Der Vorgänger von Knoten C ist Knoten B, welcher nach Knoten A folgt.

Der kürzeste Weg zum Knoten E ist also der Weg von A über B nach C zu E mit Gesamtkosten von 250.

Übungsfragen

#1. Was versteht man unter dem Dijkstra Algorithmus?

#2. Wie wird der Dijkstra Algorithmus angewendet?

#3. “Der Dijkstra Algorithmus dient der Findung des kürzesten Wegs innerhalb eines Graphen von einem Start- zu einem Endpunkt” - diese Aussage ist:

#4. “Der Dijkstra Algorithmus wird beispielsweise in Routenplanern und Navigationsgeräten eingesetzt.” - Diese Aussage ist:

#5. “Der Dijkstra Algorithmus kann auch in Graphen mit negativen Kantengewichten angewendet werden.” - diese Aussage ist:

Fertig

Ergebnis

Könnte dich auch interessieren:

Bellman Ford Algorithmus - Anwendungsbeispiel: Gegebener Graph

Bellman Ford Algorithmus

Um den kürzesten Weg in einem gewichteten Graphen zu ermitteln, kann der Bellman Ford Algorithmus eingesetzt werden. Auch bei Graphen, … weiterlesen >>

Prim Algorithmus - Anwendungsbeispiel: Finaler Graph

Prim Algorithmus

Der Prim Algorithmus wird genutzt, um den minimalen Spannbaum eines Graphen zu finden. Er kann in Graphen genutzt werden, die … weiterlesen >>

Kruskal Algorithmus - Anwendungsbeispiel: Gegebener Graph

Kruskal Algorithmus

Der Kruskal Algorithmus dient der Ermittlung des minimalen Spannbaums eines zusammenhängenden und gewichteten Graphen. Wir zeigen dir in diesem Kapitel, … weiterlesen >>

Greedy Algorithmus

Greedy Algorithmus

Ein Greedy Algorithmus ist eine Methode der Problemlösung, welche darauf ausgelegt ist, möglichst schnell eine Lösung zu finden. Diese muss … weiterlesen >>

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … weiterlesen >>

Nichts passendes dabei?

Erkunde andere Fachbereiche oder benutze die Suchfunktion. Falls Du keine Antwort auf Deine Frage findest, schick uns gerne eine Nachricht, wir versuchen dann passenden Content für Dich zu schaffen.

Zur Übersicht
Oder lieber die Suche benutzen?
  • Eselsbrücke
  • |
  • Buchungssatz
  • |
  • Formeln
  • |
  • Beispiele
  • |
  • Grafiken
  • |
  • Definition
  • |
  • Übungsfragen
  • © BWL-Lexikon.de
  • Datenschutz
  • Impressum
  • Cookie Einstellungen
Fehler gefunden?

Danke, dass du dir die Zeit nimmst, uns dein Feedback zu geben. Bitte beschreibe so genau wie möglich wo du einen Fehler gefunden hast.