Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt


Kombinatorische Optimierung / Die Berechnung kürzester Wege


Die Älteren können sich vielleicht noch an die Zeit erinnern, als man sich, um eine Fahrplanauskunft zu bekommen, an einem Bahnhofsschalter in eine Schlange einreihen musste, in der man langsam an die Spitze robbte bis man nach einer Viertelstunde seine Frage vorbringen konnte. Die Jüngeren werden eine Internetseite der Bahn AG aufrufen und (nur gebremst von der Kapazität der Server und der Netze) in kurzer Zeit mehrere Verbindungsalternativen generieren.

Diese Fragestellungen, in einem Verkehrsnetz einen kürzesten, schnellsten oder kostengünstigsten Weg zwischen einem Startpunkt und einem Zielort zu bestimmen, tritt auch auf bei Routenfindern, die uns helfen, den kürzesten Weg in den Urlaub zu bestimmen, oder bei Telematikdiensten, die helfen, Staus geschickt zu umfahren.

Die Größe der zugrundeliegenden Netze, die Vielzahl anfallender Anfragen, die sich unter Umständen dynamisch verändernden Verkehrsbedingungen und der Zwang, kurze Antwortzeiten einzuhalten, machen es notwendig, schnelle Lösungsverfahren und geschickte Datenstrukturen einzusetzen. Wir werden in den folgenden Abschnitten das klassische Lösungsverfahren behandeln und danach über verschiedene Datenstrukturen und Modifikationen des Grundansatzes sprechen.

Zur einfachen Darstellung des Problems verwenden wir die Sprache der Graphentheorie, die wir im nächsten Abschnitt kurz einführen.