We want to implement Public Transport Guide for Android. Inputs will be beginning and destination point. Outputs will be the directives that tell how can be gone to the destination with using buses, subways,... e.c This is not easy for big cities and we must have a well-designed database for quick answer. Tranport algorithm must give optimum lines to the passanger. I wanna see your precious ideas for database and algorithm design. Thank you very much for answers.
Asked
Active
Viewed 363 times
1 Answers
0
Most likely you will need a graph there to calculate shortest path.
Your graph will be G=(V,E) such that V = {all possible stations} and E = {(u,v) | there is a transport connecting station u to station v}.
If your graph cannot fit into memory [which is probably the case for a big city], you might want to make a function successors(u) = { v | (u,v) in E } which will allow you to calculate the graph on the fly.
In this older question there is some discussion how to efficiently find a path between two vertices in a dynamic environment similar to the one you are describing.
-
we don't have distance or time, only the route (example: 32-51-12-65-45, numbers are station id). Should we still use graph? – fiasco Feb 06 '12 at 20:33
-
@user1193197: Even without time, using graphs can give you a lot of information. You can run a simple [BFS](http://en.wikipedia.org/wiki/Breadth-first_search) on it to find a path with minimum number of switches - for example. So: yes, for these kind of problems, I'd say a graph is a good choice. – amit Feb 06 '12 at 20:35
-
as @amit suggested you should use graphs and since you don't have any distance/time you can use `0` for these values. reason that i am asking to use `0` is that in future, it might save lot of new implementation for next version. – Em Ae Feb 06 '12 at 20:46