CareerCup

Represent the problem as a graph: train as edge (directed), station as vertex
Use dijkstra's shortest distance path to get shortest distance from any given start to all ends.

Create a Node<A,T> for each stop S at time T. There would be 24*4 nodes for each city for each day.

For each train with n stops, create n^2 edges between appropriate nodes. The cost of an edge would be the fare. The edge includes seat availability information.

For transfers, create a special zero cost "local edge" from Node<S,T1> to Node<S,T2> , for each S, if T1 earlier than T2 by fixed amount of layover time. These edges can be built into the shortest path algorithm and need not be represented using data.

For travel between stops S1 to S2, use shortest path algorithms like Dijkstra and A* to find shortest route from Node<A,T1> to Node<B, *>. Limit/Bound the shortest path to maximum of two trains and one "local edge".

Train data can be maintained in database as an adjacency matrix.

Update graph data structure regularly by
1. Removing Nodes and Edges from past times
2. Adding Nodes and Edges for new routes as they arrive (typically a few months ahead of time).
3. Updating data when train times are updated
4. Updating availability for edges as tickets are purchased

This can be done using another approach .i.e

For every pair of station , simply use brute force approach to calculate the path between the both .
This is a lot easy to implement .

Now the result can be stored in database easily and queried easily.

The scalability depends on number of queries the site is getting .

Create a graph to represent the system
Use BFS to find shortest path.

Create a graph to represent the system.
Use BFS to find the shortest path