Gerichtete Graphen mit SQL lösen – Teil 1

Eine einfache Sicht (View) kann den Code in diesem Beispiel etwas vereinfachen. Die Sicht kann die Daten für die nächste Zwischenstation aus dem Pfad in FARETEMP berechnen, basierend auf einer Zwischenstation in FARES:

Der Algorithmus ist recht einfach: Zuerst wird die Tabelle FARETEMP mit den Daten aus der Tabelle FARE als erste Zwischenstation gefüllt. Dann werden alle soeben eingefügten Werte benutzt, um alle möglichen Pfade mit zwei Zwischenstationen zu erstellen. Dies wird fortgesetzt, solange neue Pfade zwischen zwei Knoten erstellen werden können. Diese Schleife wird verlassen, wenn alle möglichen Pfade zwischen den Knoten beschrieben sind. Man könnte auch die erste Einfügung einschränken, um die zu ladenden Datenmenge zu reduzieren, falls man nur an einer bestimmten Ausgangsbedingung interessiert ist. Hier der Code nur zum Auffinden aller Pfade:

Die entsprechende Ausgabe zeigt Tabelle A.

Mit den obigen Daten gibt es allerdings noch ein kleines Problem: Die Daten stellen die Menge der kürzesten Routen zwischen einzelnen Punkten dar (kleinste Zahl der Zwischenstationen). Allerdings ist die Direktverbindung von London nach Sao Paulo nicht die billigste Möglichkeit.

Um die preiswerteste Verbindung zu finden, muss die Schleife so geändert werden, dass eine Route durch eine billigere ersetzt wird, wenn eine solche bei einer Zwischenstation gefunden wird. So sieht der entsprechende Code aus:

Die entsprechende Ausgabe zeigt Tabelle B.

Der Algorithmus bemerkt, dass die Route LHR > JFK > GRU billiger ist als die Direktverbindung LHR > GRU und ersetzt diese. Die Schleife wird verlassen, sobald es keine preiswerteren Verbindungen gibt und keine weiteren möglichen Routen.