SQL / PHP I have start and end locations, but you want to find the join legs from the table

Question

I have a problem going through my tableLegs for a bus schedule to find an array of legID legs that the passenger will have to take to get from a to b, for example, the passenger wants to start with LocID of c and move to LocID of p , I would wanted the leg array to make that legID ( 01 , 02 , 04 ), hope this is easy enough to follow.

tableLegs

 ============================================= LegID startLocID endLocID departTime 01 ae 9:00 02 ei 10:00 03 im 11:00 04 iq 11:00 

tableLegStops

 ========================================= LegID stopNo LocID TripTime 01 1 a 0 min 01 2 b 20 min 01 3 c 30 min 01 4 d 40 min 01 5 e 60 min 02 1 e 0 min 02 2 f 20 min 02 3 g 30 min 02 4 h 40 min 02 5 i 60 min 03 1 i 0 min 03 2 j 20 min 03 3 k 30 min 03 4 l 40 min 03 5 m 60 min 04 1 i 0 min 04 2 n 20 min 04 3 o 30 min 04 4 p 40 min 04 5 q 60 min 

To give you a reason for what I'm trying to achieve here, this is for the bus site, where each ride consists of different legs.

Answer 1

This task is called finding the shortest path in a graph. There is an implementation of the Dijkstra algorithm to solve this problem in terms of the MySQL stored procedure.

But this will probably require you to slightly modify the structure of the tables, because the graph uses only two types of objects: nodes and edges. Therefore, you should spread your legs to the edges, and then bring your legs back after you get the shortest path around the edges.

Answer 2

You can use the A * search algorithm for this. Se http://en.wikipedia.org/wiki/A_star