# What algorithm to use for this kind of routing optimization?

Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS with a start point A and a destination point B. Now the data I have may be GPS locations with an information stating the danger of that location, and those datas are usually available for the whole city. How can I actually plot the safest and also (if possible) fastest route from A to B using my datas ?

I actually looked for the way google maps plot it's routes and I understood it used the Dijkstra's algorithm, but it doesn't seem to be adapted to my problem.

I believed google maps could actually send me back every possible routes from A to B, then I could use my datas to calculate the safest route using a TSP algorithm (probably the ACS applied to the TSP) in order to optimize the use of the datas and with edge weights corresponding to the associated safety of the sub-path ?

Or maybe another algorithm should be used ?

• What is "safest"? Nov 16, 2017 at 21:02
• Just noticed it could cause confusion. "Safest" here means the route which is the less dangerous for the person to take. Nov 16, 2017 at 21:03
• This begs the question. Given two routes, which is more dangerous? Nov 16, 2017 at 21:06
• To me, a route is more dangerous when it's danger level is high and the distance between A and B is high as well. Let's take two routes, one that has a danger level of 10 and one of 8. First's distance is 10 km and second is 100 km. To me the second one would be the most dangerous. Nov 16, 2017 at 21:20

According to another interpretation, the danger of a route is the maximum of the dangers of the individual stretches. In this case you can use binary search to reduce your problem to shortest path. Given a danger level $D$, you can compute the shortest distance that only goes through edges of danger at most $D$. In this way you can find the minimal $D$ for which it is possible to get from A to B, as well as (for example) the minimal $D$ for which it is possible to get from A to B using a path at most twice the distance from A to B.