Hallo,
ich möchte ein DB-basiertes Fahrplanauskunftsystem erstellen. Das heißt, ich habe Bus-Fahrpläne mehrere Linien in einer Stadt: Es gibt unterschiedliche Linien, an deren Haltestellen fahren (mit mehr oder minder regelmäßigen Ankunfts- und Abfahrtszeiten) Busse, die für jeden Abschnitt zwischen zwei Stationen eine gewisse Fahrtzeit benötigen.
Mein Ziel ist es, dass Benutzer auf einer Webseite typische Anfragen einer Fahrplanauskunft ausführen können. D.h., es gibt eine Maske mit den Feldern
Startort: _______________ Zielort:_____________________ Abfahrtsdatum & Zeit: ___________________ [Finde Verbindung!]
und ein Klick auf den Button listet mögliche Verbindungen nach Fahrtdauer sortiert auf.
Ich habe schonmal hier im Forum gesucht und diesen Thread zum Abbilden einer einzelnen Buslinie gefunden. Aber mein Problem ist komplexer, und die passende Datenstruktur ist meiner Meinung nach wohl eher ein kanten-gewichteter Graph als eine verkettete Liste. Darauf könnte man das das Single-Source-Shortest-Path Problem (z.B. mit Dijkstras Algorithmus) lösen, um den kürzesten Weg zu finden. Soweit mein Plan in der Theorie.
Aber die Frage ist: Was speichere ich in der DB, was löse ich in SQL, und was in der Sprache der Anwendung (wird wohl PHP werden)? Dijkstras Algorithmus will ich glaube ich nicht in SQL machen, aber ich will ja auch nicht den ganzen Graphen (also alle Knoten und Kanten, d.h., Stationen und Streckenfahrtzeiten) bei jeder Anfrage aus der DB holen, aufbauen, und dann alles in PHP machen.
Das Problem der Abbildung von Graphen in Datenbanken müsste recht verbreitet sein, aber ich habe verblüffend wenig Praktisches dazu gefunden (das Beste war diese DA). Oder gibt es vielleicht sogar irgendein OSS-Projekt, dass einem das Eingeben und Durchsuchen solcher Daten erlaubt?
Vielen Dank für jede Hilfe, Links sind sehr willkommen.
Tim