Hier ist eine Lösung der Aufgabe „Schnellste Zugverbindung“

Die Lösung ist eigentlich ganz einfach: Wir benutzen Dijkstras Algoritmus zur Bestimmung des kurzesten Pfades, um die optimale Zugverbindung zu finden. Allerdings nicht direkt mit dem Originalgraphen mit Bahnhöfen als Knoten und nur nach einem Fahrplan befahrbaren Kannten, sondern einen Graphen, den wir aus dem Fahrplan erstellen.

Unsere Knoten generieren wir aus den Paaren (Bahnhof, Zeit) und unsere Kannten aus den Fahrzeiten in den Zügen oder den Wartezeiten in den Bahnhöfen

In meiner Beispiellösung ignoriere ich die nötigen Umstiegszeiten und wenn es überhaupt keine Verbindung zwischen dem gewählten Ausgangs- und Zielbahnhof gibt, wird das Programm in einer Endlosschleife versinken und irgendwann mit einer Speicherfehrlermeldung abbrechen. Es zu korrigieren wäre recht einfach, aber diese Aufgabe überlasse ich dem interessierten Leser ;-)

Hier die Lösung in Java5. Sie wird unter JDK 1.4 nicht kompilierbar sein, ich wollte mit den neuen Java-Features wie den Generics, Annotations und den vereinfachten for-Schleifen rumspielen.