Sie sind hier: Startseite » Projekte 2016 » Projekt 3

Dumm gelaufen? Der kürzeste Weg

Alle kennen es, viele nutzen es: ein Navigationssystem. Mittlerweile verlassen sich manche schon blind auf ein solches System, wenn es darum geht den kürzesten oder auch den schnellsten Weg zum Ziel zu finden. Dazu muss der Computer - denn nichts anderes ist ein Navigationssystem- alle Straßen kennen und damit auch alle Entfernungen zwischen den vielen Kreuzungen.

Will man die Problematik mathematiksch in den Griff bekommen, braucht man ein Verfahren, mit dem die kürzeste Entfernung ausgerechnet werden kann. Dazu bemüht man sich zunächst einer Figur, die allgemein bekannt ist: 'Das Haus vom Nikolaus'. Spielerisch geht es darum dieses 'Häuschen' zu zeichnen, ohne den Stift absetzen zu müssen. Hier kommen die Begriffe 'Kanten' und 'Knoten' ins Spiel. Übertragen auf das Wegeproblem heißen hier die Straßen 'Kanten' und die Kreuzungen 'Knoten', die mit Zahlen gewichtet werden. Und dann gab es noch den Niederländer Edsger Wybe Dijkstra. Der hat die passende Lösung für den kürzesten Weg zwischen Startknoten und Zielknoten parat.