I want to search route from one place to one another.
The places are referenced in a SQLite Database.
I think I should make loop in the SQL query but I don't know how to perform this.
2
-
puchka, cna you refine a little bit the question? What is bus_stop_id1 and bus_stop_id2? I suppose input (call :bus_stop_id1, :bus_stop_id2). What means "search for 3 or more bus lines to join the 2 bus_stop with possible intermediary bus_stop". Are you trying to build a path like busline1 (stop1) -> busline2 -> busline3 (stop2)venergiac– venergiac2014-01-19 08:48:46 +00:00Commented Jan 19, 2014 at 8:48
-
Yes, bus_stop_id1 and bus_stop_id2 are inputs. Yes, I try to make a path.puchka– puchka2014-01-19 08:51:13 +00:00Commented Jan 19, 2014 at 8:51
Add a comment
|
1 Answer
puchka,
if I understood the question, you need a routing algorithm or graph search algorithm; in other words you cannot iterate simply on the table because you could find infinite sub-optimal solutions and you need the sortest; see Dijkastra and the related java implementation or http://www.cs.nyu.edu/~vs667/development/~DijkstraAlgorithm/ or related .
See also these SO question on
6 Comments
puchka
So have I to transform my database to a graph?
venergiac
Unfortunatly yes; any different way will be not optimal. If the databse is not big you can simply search for 2 or 3 consecutive lines and no more
Donal Fellows
@puchka Constructing all the possible routes for a bounded number of changes (e.g., 2 or 3) should leave the data relatively manageable, but it is something that you'd want to compute once and reuse rather than building on each query. (That is, you'd be denormalizing the data to improve search performance. A classic tradeoff.)
puchka
That's true but it's a mobile application so there is a constraint in the memory too.
Pranita
@puchka you got any solution?
|