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?

gnat
  • 21,442
  • 29
  • 112
  • 288
anta40
  • 281
  • 1
  • 2
  • 6
  • 3
    Is this homework? Isn't this just http://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. – riwalk Dec 19 '11 at 20:33
  • Though Dijkstra is the obvious answer, I think that the problem is more complex: traffic jams occur only at certain time intervals, meaning that path weights are not constant but depend on date of traversal, i.e., on date of departure and on path taken so far. – mouviciel Dec 20 '11 at 11:36

5 Answers5

49

Yes: Dijkstra

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

yoozer8
  • 693
  • 1
  • 8
  • 20
Martin York
  • 11,150
  • 2
  • 42
  • 70
  • 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](http://en.wikipedia.org/wiki/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 08: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 Jan 11 '12 at 04:33
  • If we make the (likely) assumption that there are coordinates attached to these nodes: The most obvious heuristic is the distance as the eagle flies. Next up would be traffic as the eagle flies. I imagine a form of spatial awareness would work too, such as "quadrant 1 is known to have more traffic", etc. – Jess Telford Feb 19 '12 at 03:20
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.

maple_shaft
  • 26,401
  • 11
  • 57
  • 131
  • 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
11

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

DKnight
  • 3,897
  • 1
  • 22
  • 31
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

Dynamic
  • 5,746
  • 9
  • 45
  • 73
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.

Michael Brown
  • 21,684
  • 3
  • 46
  • 83