Routen(Strecken) finden und auflösen.

Hallo,

ein Frohes neues Jahr erstmal an alle.

Ich beschäftige mich seit kurzem, aus jux und dollerei, mit einer Routenberechnung.

Dabei geht es Hauptsächlich um das Thema "Strecken finden durch zusammenhängende Positionen".
Das Schema kann man sich wie ein Schienennetzwerk vorstellen.

Ich möchte gerne eine Strecke von X nach Y haben, dazwischen befinden sich dann Punkte die ich zwangsläufig passieren muss, weil das Schienennetz nunmal starr ist und nicht jeder Ort an das Ziel führt (Abzweigungen usw.)

Bei >5000 Orten wirds natürlich wieder etwas haarig, da gibt es ja bekanntlich Millionen von Rechenoperationen um an das Ziel zu gelangen.

Zum Beispiel die Strecke (aus meiner Umgebung):
Herford - Melle

Der Streckenverlauf schaut dann in etwa so aus:

Herford - Hiddenhausen-Schweicheln - Kirchlengern - Bünde - Bruchmühlen - Melle

Genau diese Zwischenhalte brauche ich, als Ansatz dachte ich mir ich gebe jedem Ort den nächst möglichen "Nachbarn" in der Datenbank.

Sprich:
ID | Name | Nachbarn
1 | Herford | 2 (für Hiddenhausen-Schweicheln )
2 | Hiddenhausen-Schweicheln | 1 (für Herford) / 3 (für Kirchlengern)
3 | Kirchlengern | 2 (für Hiddenhausen-Schweicheln) / 4 (für Bünde)
4 | Bünde | 3 (für Kirchlengern ) / 5 (für Bieren-Rödinghausen ) / 6 (für Bruchmühlen)
5 | Bieren-Rödinghausen | 4 (für Bünde) / 7 (für Neue Mühle)
usw...

Aber die Rechenoperation verlangt viel zu viel Resourcen (bei gerade einmal 6 Stationen) weil ich ja erstmal jeder Abwzeigung nachgehe um an mein Ziel zu kommen. Wie schaut das ganze nur aus wenn ich mal von Flensburg nach Hamburg möchte?

Was gibt es hier für Alternativen? Wie hat die Bahn das zbs. gelöst?

Über mögliche Lösungswege (keine Vorlagen) wäre ich sehr dankbar.

VG

Shortest path problem - Wikipedia, the free encyclopedia

Danke onemorenerd, habs nun mit dem Dijkstra's Algorithmus gelöst.

Infos und Beispiele gibt es hier:

Dijkstra’s shortest path algorithm
Dijkstra's algorithm