Wie Deutschlands Bahnnetz als minimaler Spannbaum aussähe

Minimale Spannbäume kann man über Graphen ermitteln. Dies ist die Möglichkeit, alle Knoten eines Graphen mit einer möglichst kurzen Gesamtverbindungsstrecke zu verbinden.

Nehmen wir also mal an, es gäbe eine neue Schienentechnologie, die zwar teuer aber notwendig ist. Und jeder Bahnhof, der früher mit einer normalen Eisenbahn erreichbar war, soll auch mit dem neuen Zug erreichbar sein. Im Vergleich zum Schienenverlegen ist der Umbau eines Bahnhofs kein Problem, das heißt auch Provinzen können Knotenpunkte darstellen. Außerdem sollen Züge nur an Bahnhöfen auf Nebenlinien überkreuzen können.

Die letzt Annahme ist zwar etwas unrealistisch, zur Modellierung mit Minimalen Spannbäumen allerdings nötig. Wir können die letzte Annahme fallen lassen, wenn wir stattdessen ein Steinerbaumproblem lösen. Das Problem ist, dass Steinerbaumproblem extrem komplex zu berechnen sind.

Nehmen wir also die letzte Annahmen hinzu. In so einem Fall könnten wir einen minimalen Spannbaum verwenden.

Wir verwenden dazu die Bahnhof-Daten der Zugmonitor API. Diese enthalten nicht nur die Standorte der Bahnhöfe, die vom Zugmonitor erfasst wurden, sondern sogar oft deren Längen- und Breitengrad. Diese werden benötigt, um Distanzen zwischen den einzelnen Städten zu berechnen.

Zur Modellierung stellen wir jede Stadt als einen Knoten des Graphen darf und initialisieren von jeder Stadt zu jeder anderen Stadt eine Kante. Denn theoretisch sollen wir ja zwischen allen Städten Direktverbindungen bauen können.

Dann führen wir einen Algorithmus zur Ermittlung von Minimalen Spannbäumen darauf aus und zeichnen das Ergebnis: