Simulic
Deutsch

Gewichtete Graphen und kürzester Weg – Dijkstra-Algorithmus

MathematikMengen, Logik und GraphentheorieAlter 16–17

Simulic.comWird geladen …

Mit meiner Klasse nutzen

Eine Karte mit Orten wird als Graph modelliert: Knoten sind Orte, Kanten sind Straßen, Gewichte sind Entfernungen in Kilometern. Wählen Sie Start- und Zielknoten und gehen Sie den Dijkstra-Algorithmus Schritt für Schritt durch: vorläufige Markierungen vergeben, den Knoten mit der kleinsten Markierung festlegen und seine Nachbarn aktualisieren. Klicken Sie auf eine Kante, um ihre Länge zu ändern (Umleitung oder gesperrte Straße), und beobachten Sie, wie sich der kürzeste Weg ändert, zusammen mit den Knotengraden und der Bedingung für einen Eulerkreis.

Lektion: Einführung in die Graphentheorie

Was sie zeigt

Straßennetze lassen sich als gewichtete Graphen modellieren: Knoten sind Orte, Kanten sind Straßen und jedes Gewicht ist eine Entfernung in Kilometern. Der Dijkstra-Algorithmus findet kürzeste Wege von einem Startknoten aus, indem er jedem Knoten eine vorläufige Entfernungsmarke gibt: In jedem Schritt wird der noch nicht feste Knoten mit der kleinsten Marke festgelegt und die Marken seiner Nachbarn werden aktualisiert. Da alle Gewichte positiv sind, kann eine feste Marke später nicht mehr verbessert werden. Die Simulation zeigt außerdem die Knotengrade, deren Summe die doppelte Kantenzahl ist und die in einem zusammenhängenden Graphen über die Existenz von Eulerwegen und Eulerkreisen entscheiden.

So funktioniert es

Wählen Sie eine Karte sowie Start und Ziel unter Von und Nach. Drücken Sie mehrmals auf Weiter und lassen Sie die Lernenden voraussagen, welcher Knoten als Nächstes festgelegt wird und welche Marken sich ändern; mit Zurück lässt sich eine Entscheidung erneut ansehen. Vergleichen Sie die gefundene Route mit der Route über die wenigsten Straßen. Stellen Sie dann Kante anklicken auf Straße sperren/öffnen, sperren Sie eine Straße des kürzesten Weges und drücken Sie Komplett, um die neue Route zu sehen.

Einstellbare Parameter

  • Karte Stadt (7 Orte), Landkreis (9 Orte)
  • Startknoten
  • Zielknoten

Fragen zum Erkunden

  1. Warum ändert sich die Marke eines Knotens nicht mehr, sobald er festgelegt ist?
  2. Ist die Route mit den wenigsten Kanten immer die kürzeste? Welches Beispiel auf der Karte zeigt das?
  3. Welche Straßen könnten Sie sperren, damit die übrigen Straßen zusammenhängend bleiben und der Graph einen Eulerkreis besitzt?

Ähnliche Simulationen