It's true that finding the optimal solution to the problem given completely unknown data is way beyond the capabilities of SQL. That is, in theory the quickest route may be to take a trip with thousands of train changes, and the total number of possible combinations is far beyond the capabilities of any computer to process.
But in practice, I think it's safe to say that a trip with fewer train changes is almost always faster than a trip with more stops, and the traveller would probably prefer fewer train changes over a slightly shorter total trip anyway as it avoids the hassle of changing trains and the danger of missing a train because of delays. I don't know what your rail system is like (or even where you're from) but I'd guess that most trips can be completed with a modest number of train changes, probably rarely more than 2, right?
So David O'Neill's solution is basically right, though I think the query he gives is a little confused. He fails to specify the starting station, he seems to assume that the train number is unchanged throughout the trip, and perhaps most important, he calculates the time as the sum of the travel times. Surely what matters to the traveller is the total time between departure and arrival, not just the time on the train. Ten minutes on the train, four hours at the station waiting for the next train, and another ten minutes on the second train, is 4 hours and twenty minutes, not twenty minutes. Oh, and he doesn't seem to insure that the connecting train doesn't leave until after the first train arrives. A connection does you little good if the other train leaves ten minutes before you get there.
So I think the real query would be more like this:
Oh, your description of what's in the tables seems incompletet, so excuse me if I just invent my own tables with the data you would have to have to do this. Namely, you had better have:
Trip (train_number, departure_station_id, arrival_station_id, departure_time, arrival_time)
Station (station_id, station_name)
First query: Look for a direct trip:
select t1.train_number, t1.arrival_time-t1.departure_time as time
from trip t1
where t1.departure_station_id=?station_from
and t1.arrival_station_id=?station_to
order by time
If that turns up nothing, try again with one train change:
select t1.train_number, t2.train_number, t2.arrival_time-t1.departure_time as time
from trip t1
join trip t2 on (t2.departure_station_id=t1.arrival_station_id
and t2.departure_time>t1.arrival_time)
where t1.departure_station_id=?station_from
and t2.arrival_station_id=?station_to
order by time
If still nothing, try two train changes:
select t1.train_number, t2.train_number, t3.train_number, t3.arrival_time-t1.departure_time as time
from trip t1
join trip t2 on (t2.departure_station_id=t1.arrival_station_id
and t2.departure_time>t1.arrival_time)
join trip t3 on (t3.departure_station_id=t2.arrival_station_id
and t3.departure_time>t2.arrival_time)
where t1.departure_station_id=?station_from
and t3.arrival_station_id=?station_to
order by time
Etc.
You could combine all that into a single query with a UNION, filling in nulls for the extra train numbers in the shorter queries. That would have the advantage that if a trip with extra train changes really was shorter, you'd find that one. But I suspect that rarely happens. And to make the union work, you'd have to go up to the maximum number of changes -- whatever you're going to allow -- with every query, and performance would probably suck.
I haven't tried this, but I'd guess that with proper indexes the query for no-changes would be lightning fast, one change would be very fast, two changes would start getting slow, and beyond that would probably be a very long query, because the number of possible combinations would be huge. Note that a simple query like this would include absurd itineries. Like you want to go from London to Paris? We could try London to Moscow to Rome to Paris. Or London to Glasglow back to London then to Paris. Of course these would have long times and the ORDER BY would sort them to the bottom, but they'd show up as possible routes that would have to be eliminated. You could add criteria to eliminate routes that come back on themselves, but other absurd trips are harder to identify.
Have fun!