Fastest Path Algorithm

Question

I am currently implementing a navigation system for routing through Europe. So far I have had the shortest path (Dijkstra and A *). It was the easy part, now I need an algorithm for a quick way. It must be fast and reliable.

I know that this can be done simply by assigning values ​​to the quality of the road (for example, 1 highway, 2 main roads ...), then multiply these values ​​by the cost of the route and finally use Dijkstra or *, but this is not difficult enough.

I am looking for a more accurate algorithm. The map itself contains all kinds of data, such as road quality, speed limits, traffic light positions, etc., and I want to use it.

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

Answer 1

For your shortest path in your implementation, you have chosen distance as the weight for the edge.

Now, if you want to find the fastest way, just select the expected travel time as weight for the edges instead . Similarly, if you want the most reliable path, you choose some measure of "reliability" as the weight for the edges.

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

Answer 2

, " " . , , , ", ", "". .

, , . , , , " ". ? ? . , , , , .