Kürzeste-Wege-Algorithmen (Dijkstra)

Graphenalgorithmen wie Dijkstra erfordern praktisches Handeln, damit Schülerinnen und Schüler dynamische Prozesse wie Priorisierungen und Adaptionen nachvollziehen können. Durch aktive Methoden wird aus einer theoretischen Abfolge ein interaktives Erlebnis, das Denkfehler sichtbar und Lösungswege greifbar macht.

• Klasse 13
• Informatik Oberstufe: Komplexe Systeme und Theoretische Grundlagen
• 4 Aktivitäten
• 30 Min.–60 Min.

Lernziele

1. Erklären Sie die Funktionsweise des Dijkstra-Algorithmus anhand eines gegebenen Graphen mit nicht-negativen Kantengewichten.
2. Berechnen Sie die kürzesten Pfade von einem gegebenen Startknoten zu allen anderen Knoten in einem Graphen mit Hilfe des Dijkstra-Algorithmus.
3. Analysieren Sie die Zeitkomplexität des Dijkstra-Algorithmus unter Verwendung verschiedener Datenstrukturen für die Prioritätswarteschlange.
4. Entwerfen Sie eine Anwendung des Dijkstra-Algorithmus zur Lösung eines spezifischen Problems, z.B. Routenplanung oder Netzwerkoptimierung.
5. Bewerten Sie die Eignung des Dijkstra-Algorithmus für Szenarien mit negativen Kantengewichten und begründen Sie die Einschränkungen.

Forschungskreis

⏱ 45 Min.·Kleingruppen

Stationenrotation: Dijkstra-Manual

Richten Sie Stationen mit vorgegebenen Graphen ein. Gruppen führen Dijkstra schrittweise aus, notieren Distanzen und Pfade. Nach 10 Minuten Rotation und Vergleich der Ergebnisse.

Vorbereitung & Details

Erklären Sie die Funktionsweise des Dijkstra-Algorithmus und seine Grenzen.

Moderationstipp: Legen Sie für die Stationenrotation unterschiedliche Graphen mit steigendem Schwierigkeitsgrad bereit, damit schwächere Lernende schrittweise Sicherheit gewinnen.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Forschungskreis

⏱ 60 Min.·Partnerarbeit

Programmier-Challenge: Routenfinder

Schüler implementieren Dijkstra in Python mit heapq. Testen Sie mit Beispieldaten, messen Laufzeit. Erweitern Sie um Eingabe von Graphen per Datei.

Vorbereitung & Details

Designen Sie eine Lösung für ein reales Problem unter Verwendung des Dijkstra-Algorithmus.

Moderationstipp: Fordern Sie in der Programmier-Challenge eine klare Dokumentation des Code-Designs an, um die Nachvollziehbarkeit der Implementierung zu sichern.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Forschungskreis

⏱ 50 Min.·Kleingruppen

Modellbau: Stadtverkehr

Gruppen modellieren ein Stadtnetz als Graph, wenden Dijkstra an. Diskutieren reale Faktoren wie Staus. Präsentieren beste Routen.

Vorbereitung & Details

Analysieren Sie die Zeitkomplexität des Dijkstra-Algorithmus.

Moderationstipp: Nutzen Sie im Modellbau konkrete Alltagsgegenstände für Knoten und Kanten, damit die abstrakten Konzepte räumlich erfahrbar werden.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Forschungskreis

⏱ 30 Min.·Partnerarbeit

Komplexitäts-Vergleich: Messlab

Individuell oder paarweise Algorithmen mit wachsenden Graphen timen. Plotten Sie Ergebnisse, analysieren O-Notation.

Vorbereitung & Details

Erklären Sie die Funktionsweise des Dijkstra-Algorithmus und seine Grenzen.

Moderationstipp: Bereiten Sie für den Komplexitäts-Vergleich vorab Graphen mit bekannten Größen vor, damit die Messungen reproduzierbar und vergleichbar bleiben.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit manuellen Simulationen, um die Grundidee des Algorithmus zu verankern, bevor sie zur Programmierung übergehen. Wichtig ist, Fehlerkultur zu fördern, etwa durch gezieltes Einbauen negativer Gewichte in Aufgabenstellungen, um die Grenzen des Verfahrens zu erkunden. Vermeiden Sie zu frühe Abstraktion – erst wenn das Konzept sitzt, folgen komplexere Implementierungen oder Analysen.

Was Sie erwartet

Am Ende der Einheit können Schülerinnen und Schüler den Dijkstra-Algorithmus selbstständig auf verschiedene Graphen anwenden, seine Grenzen erklären und die Effizienz unterschiedlicher Implementierungen vergleichen. Erfolg zeigt sich im präzisen Berechnen von Pfaden und im Erkennen von Fehlern in falschen Anwendungen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Stationenrotation hören einige Schülerinnen und Schüler den Hinweis, dass Dijkstra überall funktioniert.

Was Sie stattdessen lehren sollten

Während der Stationenrotation lassen Sie die Schülerinnen und Schüler einen Graphen mit negativen Gewichten manuell durchlaufen. Stoppen Sie die Simulation, wenn falsche Pfade erkannt werden, und lassen Sie sie beschreiben, warum der Algorithmus hier versagt.

Häufige Fehlvorstellung

In der Programmier-Challenge wird behauptet, die Laufzeit sei immer quadratisch.

Was Sie stattdessen lehren sollten

Während der Programmier-Challenge analysieren die Schülerinnen und Schüler die gemessenen Laufzeiten ihrer Implementierungen. Fordern Sie sie auf, die Ergebnisse mit den theoretischen Komplexitäten zu vergleichen und zu erklären, warum unterschiedliche Heaps zu unterschiedlichen Zeiten führen.

Häufige Fehlvorstellung

Im Modellbau wird angenommen, dass Dijkstra nur den kürzesten Pfad zwischen zwei festen Punkten findet.

Was Sie stattdessen lehren sollten

Während des Modellbaus bitten Sie die Lernenden, die Distanzen zu allen Knoten zu berechnen und die Ergebnisse zu vergleichen. Fragen Sie nach dem Mehrwert dieser Information für die Verkehrsplanung, um das Missverständnis aufzulösen.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Stationenrotation 'Dijkstra-Manual' geben Sie einen kleinen Graphen aus und bitten die Schülerinnen und Schüler, die ersten drei Schritte des Algorithmus mit Distanz- und Vorgänger-Arrays zu dokumentieren. Fragen Sie nach dem Grund für die Auswahl des nächsten Knotens.

Diskussionsfrage

Nach der Programmier-Challenge 'Routenfinder' stellen Sie die Frage, unter welchen Umständen Dijkstra nicht die beste Wahl ist. Lassen Sie die Schülerinnen und Schüler Beispiele mit negativen Gewichten nennen und die Gründe für das Versagen erklären.

Lernstandskontrolle

Während des Modellbaus 'Stadtverkehr' lassen Sie jede Schülerin und jeden Schüler eine reale Anwendung des Dijkstra-Algorithmus beschreiben und in einem Satz die Hauptidee zusammenfassen. Ergänzen Sie die Aufgabe um eine mögliche Einschränkung des Algorithmus.

Erweiterungen & Unterstützung

• Fordern Sie fortgeschrittene Lernende auf, den Dijkstra-Algorithmus mit einer Fibonacci-Heaps-Implementierung zu vergleichen und die Performanzunterschiede zu messen.
• Unterstützen Sie Lernende mit Schwierigkeiten durch vorgegebene Tabellenvorlagen für die manuelle Berechnung oder durch Schritt-für-Schritt-Anleitungen mit Lückentexten.
• Vertiefen Sie mit einer Diskussion über Echtzeitanwendungen wie Navigationssysteme, die Dijkstra nutzen, und fragen Sie nach Kompromissen zwischen Geschwindigkeit und Genauigkeit.

Schlüsselvokabular

Graph	Eine Datenstruktur, die aus einer Menge von Knoten (Ecken) und einer Menge von Kanten besteht, die Paare von Knoten verbinden.
Kantengewicht	Ein numerischer Wert, der einer Kante in einem Graphen zugeordnet ist und oft Kosten, Entfernung oder Zeit repräsentiert.
Prioritätswarteschlange	Eine abstrakte Datenstruktur, die Elemente mit einer Priorität speichert und das Element mit der höchsten Priorität effizient abruft.
Distanzvektor	Eine Datenstruktur, die die aktuell kürzeste bekannte Distanz von einem Quellknoten zu jedem anderen Knoten im Graphen speichert.