Hier meine Beispiellösung: http://www.grayman.de/blog/verschiedenes/training/zugverbindung2.html

Die Aufgabe ist ziemlich komplex formuliert, ist aber ziemlich einfach. Sie ist von Dijkstras Algoritmus bereits gelöst. Man mus nur den usprünglichen Graphen in einen neuen gerichteten Graphen umwandeln.

Bei der 1. Aufgabe wandelt man jeden Knoten K in eine unendliche reihe von von Knoten (K,t0), (K,t1), ... Die Zeiten t0, t1 usw. sind die Zeiten an denen ein Zug in K ankommt oder aus K abfährt. Die Knoten (K, tn) und (K, t(n+1)) sind mit einer neuen (Warte-)Kante verbunden, deren länge t(n+1)- tn ist. Fährt ein Zug von K um t ab und kommt ohne zwischenzuhalten in L um s an, sind die neuen Knoten (K, t) und (L, s) mit einer (Fahr-)Kante verbunden, denen Länge s-t ist. Die Aufgabe kann so umgewandelt werden, dass wir den kurzesten Pfad zum einem Knoten aus der Menge (K, *) suchen. Der umgewandelt Graph ist zwar unendlich, das ist aber kein Problem, weil Dijkstras Algoritmus immer den nächstgelegenen Knoten aus der Menge der noch nicht bewerteten Knoten auswählen muss und da unsere unendliche Menge sortiert ist, können wir ein Minimus leicht finden.

Bei der 2. Aufgabe funktioniert es genauso, nur wird die länge der Kanten durch das Fahrgeld bestimmt. Falls wir miz Zuschlägen rechnen möchten, muss jeder ursprüngliche Knoten in mehrere Knoten-Zeitlinien umgewandelt werden: (K, t, z1, z2, z3, ..). Dabei ist zi = 0 wenn der Zuschlag Zi nicht gekauft wurde und 1 wenn man ihn kaufen muss. Zwischen diesen Knoten liegen (Zuschlags-)Kanten deren Länge dem Preis des Zuschlages entspricht.

Gewinner

Der Gewinner ist UdoStenzel, der als einziger teilgenommen hat und die richtige Lösung präsentierte. Herzlichen Glückwunsch! :-)

Lösung von Udo

Das ganze läuft auf die Suche des kürzesten Weges in einem Graphen hinaus. Der Graph ist abstrakt, jeder Knoten darin repräsentiert ein Paar aus Zeit und Ort. Natürlich sind nicht alle Knoten interessant, nur die, an denen ein Zug ankommt oder abfährt oder die mit der gewünschten Abfahrts- oder Ankunftszeit zusammenfallen. Da die Zeitskala offen ist, ist der Graph im Prinzip unendlich, aber das ist erstmal nicht schlimm. Kanten existieren jeweils zwischen den Knoten, die durch Züge verbunden sind und zwischen Kanten mit gleichem Ort aber verschiedener Zeit. Die Kanten werden mit den Kosten beschriftet, gleichgültig, wie die jetzt definiert sind.

Alle Anfragen laufen jetzt darauf hinaus, den kürzesten Weg von einem gegebenen Punkt zu einer menge gegebener Punkte zu finden oder die mit gegebenen Ressourcen erreichbaren Punkte zu ermitteln. Ersteres geht mit A*-Suche, letzteres mit billiger Breitensuche. Für den A* braucht man noch eine Kostenschätzung für den Abstand zweier Punkte, im Zweifelsfalls funktioniert es, immer 0 zu schätzen.

Komplexität des A* ist quadratisch in der Anzahl Knoten, wobei hier wohl nur die Knoten in einem gewissen Zeitintervall zählen, Breitensuche ebenfalls. Praktisch ist beides billiger, der A* wird nahezu linear, wenn man ihn mit einer guten Schätzung versorgt. Mehr Details würde ich bereits in Code gießen, sonst passieren zu viele Flüchtigkeitsfehler.

Achja, der unendliche Graph. Der wird natürlich als Funktion repräsentiert, die zu einem gegebenen Knoten die Nachbarn ergibt. Dann nimmt er nur noch endlich viel Speicher weg.