Dijkstra algorithm alternatives - shortest path in graph, bus routes

Question

i am using slightly modified Dijkstra algorithm in my app but it`s quite slow and i know there have to be a lot better approach. My input data are bus stops with specified travel times between each other ( ~ 400 nodes and ~ 800 paths, max. result depth = 4 (max 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 complicated graphs where e.g. main city(node) does have 170 connections to different cities is Dijkstra slower (~ more then 5 seconds) because compute all neighbours first one by one as it`s not "trying" to reach target destination by some other way... Could you recommend me any other algorithm which could fit well ?…

Accepted Answer

Sounds like you're looking for A*. It's a variant of Djikstra's which uses a heuristic to speed up the search. Under certain reasonable assumptions, A* is the fastest optimal algorithm. Just make sure to always break ties towards the endpoint.

There are also variants of A* which can provide near-optimal paths in much shorter time. See for example here and here.

Bellman-Ford (as suggested in your question) tends to be slower than either Djikstra's or A* - it is primarily used when there are negative edge-weights, which there are not here.

Dijkstra algorithm alternatives - shortest path in graph, bus routes

Solution

Problem