Hintergrund: Das Kürzeste-Wege-Problem

Unter dem Kürzeste-Wege-Problem versteht man die Fragestellung "Finde den besten Weg von S (Start) nach Z (Ziel)". Dabei stellt sich zuerst die Frage, was meint eigentlich "bester Weg"? Den längenmäßig kürzesten Weg? Oder den schnellsten? Vielleicht ja auch den bequemsten oder den schönsten?
Beispiel-Anwendungen aus dem Bereich des Kürzesten-Wege-Problems:
  • Wie fahre ich am besten mit der U- bzw. S-Bahn vom U/S-Bahnhof Yorckstr. zum U-Bahnhof Karl-Marx-Str.? Eine Situation, in der auch Schüler häfiger sind. Allerdings stellen sie sich selten bewusst diese Frage. Für Strecken, die sie häfig fahren, kennen sie den ihnen am besten erscheinenden Weg. Andere Strecken wählen sie intuitiv oder zählen die Stationen aus. Nun ist das Berliner U- und S-Bahn-Netz verhältnismässig ein Graph mit sehr wenig Knoten (Stationen). Hier mag Auszählen noch funktionieren.
  • Ein bekannte Situation, bei der Auszählen nicht mehr so einfach ist, sind die Routenplaner im Internet. Z.B.: Was ist der kürzeste Weg mit dem Auto von Berlin nach Stuttgart? Jenachdem, ob man den kürzesten Weg nach der Zeit oder nach Kilometern wählt, werden verschiedene Wege ausgegeben. Auch die Bahn arbeitet beim online-Fahrplandienst mit Graphenalgorithmen.
  • Es gibt auch Beispiele, in denen nicht so offensichtlich ein Weg gesucht wird. Landkarten werden z.B. auch mit diesen Algorithmen aus Satellitenbilden gewonnen. Modelliert werden die Bilder dabei als Graphen, indem als Knoten die einzelnen Pixel genommen werden und jeweils eine Kante die Nachbarpixel verbindet. Die Helligkeitsunterschiede zwischen zwei benachbarten Pixeln sind dann die Kantengewichte. Mit dem Algorithmus werden immer Kanten mit möglichst geringem Kantengewicht gewählt, das heißt, der Weg verbindet immer Pixel mit möglichst gleichen Helligkeitswerten. Sehr ähnliche Helligkeitswerte haben natürlich die verschiedenen Pixel eines Objektes, z.B. von Straßen.

weiter >