Sam
Moderator
Premium Member
Registered: 24th Dec 99
Location: West Midlands
User status: Offline
|
I guess this is probably partly/mostly a mathematical question? But here goes my following example scenario...
You are creating a program that offers you a list of ways to get from one train station to another.
Let's say you want to travel to Worcester Shrub Hill from Birmingham New Street.
The 3 ways I personally know of doing this journey are:
- Birmingham New Street direct to Worcester Shrub Hill
- Birmingham New Street > Smethwick Galton Bridge > Worcester Shrub Hill
- Birmingham New Street > Droitwich Spa > Worcester Shrub Hill
How would you create such a program and make it 'know' that it can go to different points via other points? 
|
John
Member
Registered: 30th Jun 03
User status: Offline
|
I'm not a programmer but I'd want a database that contained the station with links to the stations that connected.
You'd then need to traverse the database in the most efficient way to compare all the links.
|
AndyKent
Member
Registered: 3rd Sep 05
User status: Offline
|
Interesting question, be interested to know the answer.
I suspect I could build something with a limited number of stations but it'd probably be grossly inefficient and rely on processing power rather than intelligence.
|
Dom
Member
Registered: 13th Sep 03
User status: Offline
|
As John said but personally i'd opt for someone else's API 
|
John
Member
Registered: 30th Jun 03
User status: Offline
|
Actually, is this not just the travelling salesman problem?
|
Ian
Site Administrator
Registered: 28th Aug 99
Location: Liverpool
User status: Offline
|
Usually Dijkstra's algorithm, computationally quite expensive with a relational database as you need as many recursive joins as there are probably nodes in your route.
In essence, you have a table of stations, then another table which station id 1 and station id 2 and the distance/time/whatever
You keep querying the distances table and sum up all the distances, and order the result set by the sum so that the top results are your path candidates.
You'll get lots of wacky solutions which are very long which you discard.
I'd probably combine it with some sort of knowledge of where the stations physically were and bound on that so you're not talking about Liverpool stations if your start and finish destinations are both in Birmingham for example. OS Code Point would help you there assume you also have postcodes for the stations.
The other problem is that if you don't have the database it will very time consuming to create. Number of rows is the number of stations, squared, minus any prohibited combinations - trains which don't stop or different lines which don't give access to the same stations.
[Edited on 07-07-2012 by Ian]
|
AndyKent
Member
Registered: 3rd Sep 05
User status: Offline
|
Here we to - http://algo2.iti.kit.edu/documents/routeplanning/weaOverview.pdf
|
Sam
Moderator
Premium Member
Registered: 24th Dec 99
Location: West Midlands
User status: Offline
|
So what would happen if say for example you wanted to travel from Birmingham New Street to Liverpool Lime Street if there was no direct route?
|
Chris
Premium Member
Registered: 21st Sep 99
User status: Offline
|
There is a direct route i used it the other day departs  1 and :36
www.thetrainline.com kinda does just what you are asking, even give you ticket prices.
[Edited on 08-07-2012 by Chris]
|
Ian
Site Administrator
Registered: 28th Aug 99
Location: Liverpool
User status: Offline
|
quote:
Originally posted by Sam
So what would happen if say for example you wanted to travel from Birmingham New Street to Liverpool Lime Street if there was no direct route?
When the route is found, the number of nodes / travel time per node is summed and that is your route.
In your original example you are also displaying the runners up to the direct route, BNS to Liverpool the runners up (ie. not direct) are the top of the node/station count / distance / time whatever your weight is in the data.
|
