Am Freitag waren es zwei Jahre seit dem Tod des niederländischen Computerwissenschaftler Edsger W. Dijkstra, der unter anderem auf die Gefahren des GOTO so eindrucksvoll hingewiesen hat.

Zu seinen bekanntesten Beiträgen zu der Computerwissenschaft gehört der Algoritmus zur Bestimmung des kurzesten Pfades zwischen zwei Knoten eines (gerichteten) zusammenhängenden Graphen.

Beschreibung

Stellen wir uns mal vor, dass wir nicht den kürzesten Pfad zwischen zwei Knoten des Grafen suchen, sondern die „schnellste“ Verbindung. Und dass wir statt einfach den Kanten zwischen den Knoten zu folgen, nur die „Bahn“, die zwischen den Knoten fährt, benutzen dürfen. Beim Umsteigen müssen wir in einem Knoten so lange warten, bis der nächste Zug kommt.

Als Eingabe haben wir einen Fahrplan aller „Züge“, die zwischen den Knoten regelmäßig fahren. (um die Aufgabe einfacher zu machen, gehen wir davon aus, dass der Fahrplan für jeden „Tag“ der gleiche ist).

Aufgaben

1. Entwickle einen Algorithmus, mit dem man für einen definierten Startknoten und Startuhrzeit die schnellste Zugverbindung zum definierten Zielknoten gefunden wird.
2. Zeit ist Geld. Jede Stunde, die wir unterwegs sind, kostet uns P_h, jeder gefahrene Kilometer kostet uns P_km. Für bestimmte schnelle Züge muss man einen Zuschlag zahlen (der Zuschlag kostet einen festen Betrag für die komplette Reise). Entwickle einen Algorithmus, mit dem man für einen definierten Startknoten und Startuhrzeit die billigste Zugverbindung zum definierten Zielknoten gefunden wird.

Lösung

Ja, ja. Ich werde hier eine Beispiellösung beschreiben. Aber jetzt noch nicht. ;-)

(Wer schummeln will: hier findet man die Antwort auch.)