Fastest-path algorithm

Question

Hi, I'm currently implementing a navigation system for routing through Europe. So far, I have shortest path implemented (Dijkstra and A*). It was the easy part, now I need some algorithm for fastest path. It has to be fast and reliable.

I know it can be done just by assigning values to a road quality (for example 1 highway, 2 main road ...), then multiply these values with route costs and finaly use Dijkstra or A*, but it's not sophisticated enough.

I'm searching for more accurate algorithm. The map itself contains all kinds of data, like road quality, speed limits, traffic lights positions etc., and I want to use it.

Are there any good algorithms for this? Or at least a good modification of A*?

Answer 1

It depends what you mean by 'fastest' path. If you knew the average speed you could travel on on each segment of the road, then you could just convert your graph so the edges contain "time taken to travel" instead of "distance". Then you can do a shortest-path algorithm over the new graph.

It seems like you mentioned that's not good enough, though. I think the problem is that you have to define what 'fastest' means. How does road quality affect speed? What about traffic lights? These are all variables you have to find a way to account for. If you as a human don't know the metric you'll be using, it'll be hard to get the computer to do it.

Answer 2

In your implementation for shortest path you chose distance as weight for an edge.

Now if you want to find the fastest path, you simply pick expected travel time as weight for the edges instead. Similarly, if you want the most reliable path, you pick some measurement of "reliability" as weight for the edges.

A* (although not always optimal, as it relies on a heuristics function) is probably your best option for this type of application. If your A* is not accurate enough, I suggest you either go for Dijkstras or spend some time on tweaking and improving your heuristics function.