CODEWITHSUNDEEP
sqlalgorithmgraph
user3162968
user3162968

Reputation: 1046

Application searching railway connections

I am managing a project which can be described as below.

Application should display train connections from city A to city B, with optimization on grounds of total travel time, total kilometres, waiting time on station etc. It has more requirements, but they are not so hard so I can handle it alone.

I would like to receive proposition for implementation. I was thinking about indirected graph where cities are vertices and railways are edges. Every single railway would have start city, end city, length and maybe some other parameters.

The main problem is following: in a database there will be trains with specified start station, end station and intermediate station, with given arrival and departure time. What algorithm would you propose that would be able to find the best connection from city A to city B?

I am thinking about the following: there would be matrix of dimension A[n][n], where n is the number of cities. Let a and b be ID of cities A and B. If there exists direct train from A to B, A[a][b]=1, else A[a][b]=0. If there does not exist such cennection, system tries to find connection through city which is connected with A and with B. Is it efficient solution?

Upvotes: 0

Views: 162

Answers (1)

gbjbaanb
gbjbaanb

Reputation: 52679

Create edges for each segment of track, so you can model junctions and sidings and the like. Nodes combine each of these edges together, they don't need to be only stations.

Then get yourself boost::graph and use one of its algorithms to do all the hard work for you :) Suggested ones are A* or Dijkstra.

Upvotes: 3

Related Questions