Entwicklung einer Fahrplanauskunft

[Furtbichler]

Zitat von NamenLozer:

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben.

Dann weißt Du ja mehr als ich

Zitat:

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

Nein. Lies meinen Ansatz genau. Eine Fahrt von A->B dauert 5 Minuten, Umsteigen bei B dauert 10 Minuten. Ergo ist fahren und umsteigen ein und dasselbe: Ein Übergang von A nach B, der X Minuten dauert.

Also:
Fahrplan:
Bus 1 fährt von A-10->B-20->C
Bus 2 fährt von B-10->C

Wenn A an B ankommt, fährt #2 3 minuten später ab.
Ich führe einen neuen Knoten ein (B1)
Bus 2 fährt dann nicht von B ab, sondern von B1 -> C (10 Minuten)
Eine neue Kante: Umsteigen von B->B1 (3 minuten).

Also hast Du wieder einen simplen gerichteten Graphen. Nix mit Dimension. Nur eben die Funktion, die die Fahrt/Wartezeit von A nach B ausrechnet, benötigt die Ankunftszeit bei 'A'.

Bei uns wäre das also:
Abfahrt bei A um 15:10 nach B.
Ankunft bei B um 15:20

Bus #2 fährt um 15:23 ab
also bekommt die Kante B->B1 den Wert 3 (Minuten)

Wenn wir bei A um 15:00 losfahren würden, kämen wir bei B um 15:10 an.
Dann bekommt die Kante B->B1 den Wert 13 (Minuten)

verstanden?