# Algorithm to determine fastest route?

Let's say we're going from 1 to 5. The shortest route will be 1-4-3-5 (total: 60 km).

We can use Dijkstra's algorithm to do that.

Now the problem is, the shortest route is not always the fastest one, because of traffic jams or other factors.

For example:

• 1-2 is known to have frequent traffic jams, so it should be avoided.
• Suddenly a car accident happens along 4-3, so it should be avoided too.
• Etc...

So probably we can speed on the route 1-4-5, because of no traffic jams/accidents, so will arrive at 5 faster.

Well that's the general idea, and I haven't think about more details yet.

Is there any algorithm to solve this problem?

• Is this homework? Isn't this just en.wikipedia.org/wiki/Travelling_salesman_problem for traversing a weighted graph? Dec 19, 2011 at 16:42
• @StuperUser: No, TSP is a circuit of all nodes without duplicates. In the sample case, there's no need to hit node 2, for example. Dec 19, 2011 at 17:03
• @DavidThornley I see. So Dijkstra is for shortest route on a weighted graph? And TSP is traversal visiting every node? Dec 19, 2011 at 17:28
• @Stuper: Shortest traversal, yes Dec 19, 2011 at 20:26
• @StuperUser, just FYI, TSP is a strongly NP-Complete problem with no solution that can be run in polynomial time. ... So now you know. Dec 19, 2011 at 20:33

Since you brought congestion into the picture, be careful you don't get caught by Braess' Paradox. If everyone chooses the optimal path, it results in worse travel time for everyone.

Yes: Dijkstra

Dijkstra works just as well for this situation.
You just use time rather than distance as the weight of each arc.

• Typically the 'distance' in Dijkstra would be weighted for all sorts of things, cost/tolls, freeway preference, speed limits - using just the distance is only the simplest niave approach. This is what makes the algorithm so clever Dec 19, 2011 at 17:56
• Although Dijsktra will do, I would generally choose A* for any serious pathfinding work; heuristics will help a lot. Dec 19, 2011 at 18:48
• Link: A* search algorithm. It's an extension of Dijkstra's method. Dec 19, 2011 at 20:15
• As long as there is an applicable heuristic, A* is going to be superior to Dijkstra's (in terms of performance). Dec 23, 2011 at 8:28
• An admissible heuristic would be somewhat challenging to find here considering we seem to take into account many factors (such as traffic jams). Jan 11, 2012 at 4:33

Yes. Dijkstra's algorithm will solve this problem.

The problem in your case is that you automatically assume the shortest path equates to distance travelled, when in fact it more appropriately equates to the COST of taking a route.

If one path has a roadblock then its COST should be higher, and the algorithm still applies.

• Yeah sorry if I didn't use the right wording. What I means is the 'most convenient route' (most minimum cost) Dec 20, 2011 at 17:21

You should just be able to replace your distance with the time between nodes and solve it the same way.

# Dijkstra

As said before, it is not only used for shortest distance. I believe this animation gives a good understanding of the "power" (for lack of a better word) of Dijkstra: