I am using a slightly modified Dijkstra's algorithm in my application, but it is rather slow and I know that there should be a much better approach. My input is bus stops with a specified travel time between each other (~ 400 nodes and ~ 800 paths, maximum result depth = 4 (maximum 4 bus changes or nothing).
Input data (bus routes):
bus_id | location-from | location-to | travel-time | calendar_switch_for_today
XX | A | B | 12 | 1
XX | B | C | 25 | 1
YY | C | D | 5 | 1
ZZ | A | D | 15 | 0
dijkstraResolve(A,D, '2012-10-10') -> (XX,A,B,12),(XX,B,C,25),(YY,C,D,5)
=> one bus change, 3 bus stops to final destination
* A->D cant be used as calendar switch is OFF
As you can imagine, in more complex graphs, where, for example, the main city (node) has 170 connections to different cities, this Dijkstra is slower (~ more than 5 seconds), because it computes all the neighbors first one by one, since it "not trying" to reach the destination in some other way ..
, ?
:
( ):
-
- ( )