Fastest-path algorithm

Question

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

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.