Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

Graph

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?

share|improve this question
3  
Is this homework? Isn't this just en.wikipedia.org/wiki/Travelling_salesman_problem for traversing a weighted graph? –  StuperUser Dec 19 '11 at 16:42
9  
@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. –  David Thornley Dec 19 '11 at 17:03
2  
@DavidThornley I see. So Dijkstra is for shortest route on a weighted graph? And TSP is traversal visiting every node? –  StuperUser Dec 19 '11 at 17:28
1  
@Stuper: Shortest traversal, yes –  BlueRaja - Danny Pflughoeft Dec 19 '11 at 20:26
2  
@StuperUser, just FYI, TSP is a strongly NP-Complete problem with no solution that can be run in polynomial time. ... So now you know. –  Stargazer712 Dec 19 '11 at 20:33

5 Answers 5

up vote 5 down vote accepted

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.

share|improve this answer

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:

Dijkstra

share|improve this answer
    
+1 for a great way to illustrate a point. –  Kris Dec 20 '11 at 10:17

Yes: Dijkstra

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

share|improve this answer
9  
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 –  Martin Beckett Dec 19 '11 at 17:56
6  
Although Dijsktra will do, I would generally choose A* for any serious pathfinding work; heuristics will help a lot. –  Mircea Chirea Dec 19 '11 at 18:48
6  
Link: A* search algorithm. It's an extension of Dijkstra's method. –  mgkrebbs Dec 19 '11 at 20:15
    
As long as there is an applicable heuristic, A* is going to be superior to Dijkstra's (in terms of performance). –  bummzack Dec 23 '11 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). –  pwny Jan 11 '12 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.

share|improve this answer
    
Yeah sorry if I didn't use the right wording. What I means is the 'most convenient route' (most minimum cost) –  anta40 Dec 20 '11 at 17:21

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.