Dijkstra - Algorithmus

Löst folgendes Problem: Wie komme ich am schnellsten von A nach B?

0.

Startstadt markieren und Kennzahl 0 zuweisen und als aktuelle Stadt.bezeichnen

1.

Von der aktuellen Stadt zu allen direkt erreichbaren Nachbarstädten gehen

... für jede Nachbarstadt Folgendes durchführen:

Summe aus der Kennzahl an der aktuellen Stadt und der Streckenlänge dorthin errechnen

- Wenn Nachbarstadt rot markiert, nichts machen
- Wenn Nachbarstadt keine Kennzahl hat, ihr die Summe als Kennzahl zuweisen,       Strecke zur aktuellen Stadt markieren
- Wenn Nachbarstadt eine Kennzahl kleiner der Summe hat, nichts machen
- Wenn Nachbarstadt eine Kennzahl größer der Summe hat,
   dortige Kennzahl sowie die Markierung streichen und
   Summe als neue Kennzahl zuweisen,
   Strecke zur aktuellen Stadt markieren

2.

Bei Städten mit Kennzahl, aber nicht markiert, die Stadt mit der kleinsten Kennzahl wählen

3.

diese als aktuelle Stadt bezeichnen
Wenn mehrere Städte mit kleinster Kennzahl vorhanden, eine beliebige davon als aktuelle Stadt wählen

4.

Stadt und Strecke markieren

5.

Falls es noch unmarkierte Städte gibt - weiter bei 1.

Beispiel bei Wikipedia

Arbeitsblatt

Aufgabe: Zeichnen Sie eine fiktive Straßenkarte, abstrahieren Sie diese zu einem Wegenetz und ermitteln Sie mit Hilfe des Dijkstra-Algorithmus' die kürzeste Strecke zu einem selbst gewählten Ort!

Beispiel für eine Straßenkarte, Beispiel für eine Abstraktion dieser Karte
Zumindest eine ähnliche Straßenkarte wäre wichtig; die Abstraktion kann händisch mittels Schablone gezeichnet werden.

Hinweis: Dijkstra-Algorithmus gehört zu den gefräßigen, gierigen Strategien (greedy).
Schema: In jedem Schritt den besten "Happen" bekommen, ohne aufwendiges Backtracking.

- einfache Implementierung
- vergleichsweise sehr effizient
- nicht jedes Problem mit Greedy exakt lösbar

PDF-Datei zur Veranschaulichung

Java-Applet zur Veranschaulichung