# Sql Station To Station Problem

## Recommended Posts

Hi,I'm designing an sql system which models a metro train network. The problem I'm having is if a user specifies a start and end station how would the system calculate the route?The Tables I have are STATION (containing all the station names), LINE (which contains all the line names), and LINESTATION (containing STATION's which are interchanges to other LINES). I also need to add the direction e.g. westbound, eastbound, and the destination of the train but I don't know in which tables to put these in, or if I have to add other tables. Most of all I dont know how to calculate the route from a start station to a destination. Please help.

##### Share on other sites

Finding the shortest path is a classic artificial intelligence problem. The answer isn't an easy answer, you'll need to get some AI books and start studying them. You will need to produce a "weighted graph", where each vertex in the graph is a station and the path between any 2 vertices is given a weight, such as how long the path is. If you can produce a weighted graph there are several algorithms you can use to find the distance between any 2 vertices that has the smallest total cost.http://en.wikipedia.org/wiki/Shortest_path_problem

##### Share on other sites

Hello there,Isn't there any other way other than using a search algorithm??? Could the tables be structured in a way to find the path from one station to another. For example if Station A to B are on different metro lines couldn't you just check if they share a common subway interchange station. But I don't know how you would structure this within the tables and using queries.

##### Share on other sites

For example if Station A to B are on different metro lines couldn't you just check if they share a common subway interchange station.
Sounds like a search algorithm.Given 2 stations and the links you can travel from them, how would you know which line they're on? The database doesn't care about red lines and blue lines, all it needs to know is a set of vertices (stations) and edges (links between stations). It doesn't matter that a certain 20 edges make up the "red line", does it?What if you have a graph like this:
`A---B---C---D|   |   |   ||   |   |   |E---F---G---H`

If someone is finding the path from A to F, are you going to tell them A-E-F or A-B-F, or are you going to tell them A-B-C-D-H-G-F? How do you know what the best way is if there is more than one way?The answer is a shortest path algorithm. If you think computer scientists like Edsger Dijkstra don't know what they're talking about and you have a better idea how to solve this problem, then pretty soon everyone will know your name. If it was me building this, I would read what Dijkstra has to say.This is the way shortest path works, in a nutshell:Say you want to find all paths to H. Each node has a distance to H, H has a distance of 0 because it's the target. D and G are right next to H, so they get a distance of 1. C and F are next to D and G, so C and F get a distance of 2. Likewise, E and B get a distance of 3 because they are next to nodes with a distance of 2. So if you are at F, and you want to get to H, you can see that B has a distance of 3, and G has a distance of 1, so you go to G because it is the shortest path. This is what those algorithms try to do, find the shortest path between any two (single pair) vertices. If you want to do that with a single database lookup, you will need N^2 database tables. If you have 8 nodes, you need 64 database tables to hold that information. If you have 100 nodes, you need 10,000 tables. That's not very efficient, although it would be fast to search.

##### Share on other sites

For example, take a look at the Singapore MRT (metro) map: http://subway.umka.org/maps/singapore.gifNow, say I wanted to get from Novena on the red North South line to Jurong East (the NW terminal of the green East West Line). Soo... which way do I go? Do I go south and interchange at Raffles Place, taking the EW line south, or travel upwards and switch at Jurong East instead? Or maybe it would really be faster to use the North East line to cut across to Outram Park before continuing on the EW. Or maybe a route involving the circle line from Bishan to Buena Vista would be more optimal? Who knows? Your application needs to