Vorbereitung

nach Jens Gallenbacher: Abenteuer Informatik

Ausgangskarte

Als Beispiel wollen wir einen Weg auf einer Karte finden: Es geht von Imstadt nach Lupera.

Schritt 1

Zuerst einmal überlegen wir uns, was denn für die Aufgabe überhaupt wichtig ist. Dabei vereinfachen wir die Karte:

  • Aus den Städten werden «Knoten» mit einem einzelnen, aber eindeutigen Buchstaben
  • Kreuzungen werden zu «Knoten»
  • Strassen werden zu einheitlichen «Kanten» (wir vernachlässigen den Strassentyp)
  • Die Distanzen bleiben erhalten und werden den Kanten zugewiesen

Schritt 2

Wir können weiter vereinfachen:

  • Kreuzung-Knoten werden gleich behandelt wie Städte: Sie erhalten einen Buchstaben der noch nicht vergeben ist.
  • Kanten können gerade dargestellt werden: Dort wo sich zwei Kanten kreuzen gibt es keine Kreuzung!

Endergebnis

Was wir nun erhalten ist ein Gewichteter Graph:
Ein Graph besteht aus Kanten und Knoten. Bei einem gewichteten Graphen hat zusätzlich jede Kante ein Gewicht – bei uns die Länge der Strasse welcher durch die Kante dargestellt wird. Im Gegensatz zur Baumstruktur, darf ein Graph auch Loops beinhalten. («Rundfahrten» sind erlaubt.)

Diesen Graphen können wir nun verwenden, um automatisiert einen Weg – oder sogar den kürzesten Weg zwischen zwei Ortschaften zu finden.

Abstraktion

Wir vereinfachen, lassen alles nicht wichtige Weg – damit wir das Problem mit dem Computer darstellen und lösen können.