17

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?

6
  • 3
    Is this homework? Isn't this just en.wikipedia.org/wiki/Travelling_salesman_problem for traversing a weighted graph?
    – StuperUser
    Commented Dec 19, 2011 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
    Commented Dec 19, 2011 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
    Commented Dec 19, 2011 at 17:28
  • 1
    @Stuper: Shortest traversal, yes
    – BlueRaja - Danny Pflughoeft
    Commented Dec 19, 2011 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.
    – riwalk
    Commented Dec 19, 2011 at 20:33

5 Answers 5

Reset to default
5

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.

49

Yes: Dijkstra

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

6
  • 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
    Commented Dec 19, 2011 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
    Commented Dec 19, 2011 at 18:48
  • 6
    Link: A* search algorithm. It's an extension of Dijkstra's method.
    – mgkrebbs
    Commented 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).
    – bummzack
    Commented 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).
    – anthonyvd
    Commented Jan 11, 2012 at 4:33
16

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.

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

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

10

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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