Dumm gelaufen - der Weg zum kürzesten Weg

Arbeitsauftrag:

Mittlerweile ist das Global Positioning System - kurz GPS genannt - selbst bei Privatpersonen häufig im Gebrauch. Wie wird die Position des Gerätes bestimmt? Wie berechnet dann der Computer den kürzesten Weg zwischen zwei Punkten? Es gibt doch so viele Kreuzungen zwischen Start- und Zielpunkt.
Die Schülerinnen und Schüler beschäftigen sich in dieser Gruppe mit Wegeproblemen, einem zentralen Thema der Graphentheorie und bestimmen u. a. den kürzesten Weg vom Jugendgästehaus zum Zoo.
Vielleicht besteht auch die Möglichkeit, mit einem professionellen Gerät an der Positionsbestimmung zu arbeiten.

Umsetzung:

Zunächst
Zunächst werden die Längenangaben an alle möglichen Wege geschrieben.

Zunächst sollte man sich einem einfachen Problem widmen:
Wie kommt man am schnellsten vom Münsteraner Jugendgästehaus zum Zoo?
Dazu benötigt man zunächst einmal eine Karte und plant.
Danach reduziert man das Problem auf das Wesentliche:
Aus Straßen werden Linien und aus Straßenkreuzungen werden Knotenpunkte.

Nichts
Nichts deutet mehr darauf hin, dass es sich hier um einen Stadtplan handelt.

Danach erstellt man eine stark vereinfachte Skizze, die einem Stadtplan nicht im Entferntesten ähnelt. Hier hat man nur noch Knoten und Strecken, an die Längenbezeichnungen geschrieben wurden. Jetzt hangelt man sich von Knotenpunkt zu Knotenpunkt und stellt für jeden dieser Knotenpunkte die Entfernung vom Startknoten fest. Die kürzere Entfernung gewinnt, damit scheiden bestimmte Wege schon einmal aus.
Natürlich kann ein solches Problem mathematisch und auch per Computer berechnet werden: Man löst es mit Hilfe des Dijkstra-Algorithmus.