algorithm - is there is a route from city a to city b in no more than x days?

Question

I was in a trading firm interview, I was asked this question,

you are travelling accross the state in a buses, the buses can stop at any C possible cities and you need to find a way to go from city a to city b. There are total B buses, each of which travels between two cities. All buses travel on a daily bases, for example each bus x leaves some city c1 on day d1 and arrives at another city b1 on another day d2 (d2>d1). Assume that if you arrive at a city on day d, you can catch any bus leaving the city on day d or after.

you are given a1, b1,d1, and d2 for B buses. describe an algorithm that determines whether there exist a route from city a to city b in no more than D days, and analyze the run time.

I was initially try to model the problem in to shortest path algorithm but I could not figure out at that moment, I screwed the interview.

Answer 1

I thought if you were given a day to start from (which doesn't seem to be the case), it should be easy to apply Dijkstra's algorithm.

It's trivial to create a graph for the problem. Each node is a city, each bus is a directed edge from one node to another. The weight of an edge isn't really defined in general (we can't just take the trip time) and will be determined when we process it.

So, reduce the problem to multiple sub-problems where you know the start day, as follows:

From a there are k busses to other cities. So bus b_i goes from a to b_i from day start_i to day end_i. For each of these busses, create a sub-problem starting from b_i on day end_i (and remember start_i).

To do Dijkstra given a starting day and city:

When exploring the graph, we need to keep track of the current day.

When generating neighbors at a city c1 from day d1, for each city c2 where there is a bus from c1 to c2, we generate the earliest bus from c1 to c2 (where depart at c1 >= the current day) (if busses can take different amounts of days to get from c1 to c2, consider the earliest arrive at c2). The value of c2 would simply be the number of days from the original starting day (start_i from above) to the day the bus arrives at c2.

Optimization:

You don't need to do a complete run of Dijkstra on each subproblem, if you arrived at a city on a certain day, any next subproblem that arrives at that city on the same day would have the same path from there onward. Doing them all at the same time shouldn't be too difficult and should result in better performance than doing them one at a time.

One may be able to come up with a heuristic function to be able to apply A*.

Feel free to point out if I missed something.