Hier ist der Graph aber unendlich und man findet (in zeitlicher Dimension) an jedem Knoten einen weiteren Knoten, der nicht zum Ziel führt.
Hmmm..... Nein.
Der Graph enthält alle Bus/Bahnlinien. Die Kosten einer Fahrt sind je Kante konstant (wenn man Baustellen, Staus etc. mal ignoriert). Die Wartezeiten an den Knoten beim Umsteigen sind abhängig von der Ankunftszeit, die jedoch beim Traversieren des Knotens bekannt ist, denn man sucht ja immer den kürzesten Weg bei Abfahrt zu einem
bestimmten Zeitpunkt.
Wenn mann also z.B. am Zentralbahnhof umsteigen will, dann gibt es immer genau eine nächste Verbindung zu einem Ort X (ICE und Bummelzug sind zwei unterschiedliche Verbindungen!). Die übernächste ist irrelevant, denn dann ist man garantiert länger unterwegs. Deswegen kann man (zumindest bei der Bahn) auch angeben, wie lange man mindestens am Umsteigebahnhof warten will. Denn dann wird ggf. nicht die nächste Verbindung genommen, sondern die Übernächste.
Der Graph also endlich, aber die Kantengewichtung unvollständig und wird erst während des Suchvorganges dynamisch ermittelt. Eine Fahrtzeit kann zum Zeitpunkt X 10 Minuten sein, aber zum Zeitpunkt Y (Berufsverkehr) auch 50 Minuten. Die Wartezeit kann mal 5, mal 10 Minuten sein (gleiches Ziel). Das ist aber kein Showstopper.
Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor
Würde ich nicht machen, denn deine Lösung ist dann eine ganz andere.
Implementiere einen Optimierungsalgorithmus deiner Wahl (Djikstra wurde bereits genannt) und modelliere dabei Haltestellen und Umsteigeaktionen als einzelne Knoten. Die Verbindungen zwischen den Knoten sind Fahrt- bzw. Umsteigezeiten. Für beides schreibst Du jeweils eine Funktion
Delphi-Quellcode:
Function FahrtZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;
Function WarteZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;