6 ms·

On Dijkstra's Algorithm

72 points by hemapani 12y ago

michaelt 12y ago
Nowerdays, Google Maps is most likely using more modern algorithms, like 'contraction hierarchies' [1] - the algorithm inserts shortcuts into the graph in a structured way, so you only switch from a higher-numbered shortcut to a lower-numbered shortcut (or non-shortcut) at the very start or end of the route. This radically reduces the number of edges that need to be explored. [1] https://www.youtube.com/watch?v=-0ErpE8tQbw https://www.youtube.com/watch?v=-0ErpE8tQbw
- amelius 12y ago
  A hierarchical approach makes a lot of sense, intuitively. It makes me wonder why it took so long before such method was considered.
  - lorenzhs 12y ago
    The area of route planning research got a large boost with the 9th DIMACS Implementation challenge in 2005/06, this is where most of the research into fast and exact route planning algorithms started. (What sat nav vendors did and are still doing usually isn't exact, they were using inexact heuristics that were based on the 'natural' hierarchy in the road network)
- lorenzhs 12y ago
  Calling Contraction Hierarchies 'a variation' of Dijstra's algorithm, as the article does, is a bit of an understatement though. For anyone interested in route planning algorithms, there is a wide variety of interesting speed-up techniques. Some more key words: Arc Flags, Landmarks, Multi-Layer Dijkstra, Customizable Route Planning, Hub Labelling, Highway Hierarchies, PHAST. For transportation networks, also have a look at RAPTOR. A list of interesting references is available at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/routenplanung/index#literatur http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (the slides are in German, unfortunately)
jgrahamc 12y ago
Before there was Dijkstra's Algorithm there was still need to solve these problems. Here's a talk I gave about computing shortest paths for British Rail in 1955. https://www.youtube.com/watch?v=pcBJfkE5UwU https://www.youtube.com/watch?v=pcBJfkE5UwU
- sjtrny 12y ago
  You forgot the link.
  - jgrahamc 12y ago
    Oops. Thanks.
- elwell 12y ago
  Link says talk was given in 2012 not 1955.
  - IanCal 12y ago
    Assuming this is a serious comment, it's: Here's a talk I gave (about computing shortest paths for British Rail in 1955). Rather than Here's a talk I gave (about computing shortest paths for British Rail) in 1955. That is, the topic is computing shortest paths in 1955 for British Rail and the talk was given in 2012.
    - zimpenfish 12y ago
      I have to admit it gave me momentary pause for "Wow, I didn't think jgrahamc was -that- old".
      - jgrahamc 12y ago
        :-) True. 1955 < my_dob
    - elwell 12y ago
      Ha, no I was just kidding.
crypt1d 12y ago
FYI, one of the most popular routing protocols (used in internal networks) is OSPF[1], which is based on Dijkstra's algorithm. [1] http://en.wikipedia.org/wiki/Open_Shortest_Path_First http://en.wikipedia.org/wiki/Open_Shortest_Path_First
- windexh8er 12y ago
  When I saw the headline of the article, and being a network engineer by trade, I thought for sure this article was on OSPF. Was intrigued to see Google Maps leveraging Dijkstra's algorithm. Makes you think about traffic a bit different - I wonder if Google has the concept of backbone, stub and transit "areas" within maps? Next time I use a mapping solution I'll definitely think about it much differently, very cool. Does anyone know how costs are assigned in a mapping application that may use something like Dijkstra's? In the network world cost is derived by link speed and distance, being a general oversimplification, but I wonder how general areas are broken up into routing domains? By city or state? Very interesting...
  - varjag 12y ago
    A bunch of weighing schemes possible, including speed limit, distance, congestion and toll fees. The routing algorithms for electric vehicles seem to prioritize elevation (or rather lack of) as well, to preserve battery.
tristramg 12y ago
Dijkstra’s algorithm is well known in computer science, but as other comments say it, Google uses a much more advanced algorithm. Furthermore the complexity O(n×log(n)) we know dates from the 80’s. Many years after Dijktra’s original article. I wrote a year ago a small blog post where I tried to show the chronology: http://blog.tristramg.eu/short-history-of-routes-computation.html http://blog.tristramg.eu/short-history-of-routes-computation...
- farresito 12y ago
  Thank you for your article. Pretty interesting. Will finish reading it when I get home.
- bunderbunder 12y ago
  Paraphrasing an observation that was shared with me last week, "Dijkstra was an asshole. All his stuff runs in exponential time."
deleted 12y ago
[deleted]
csom 12y ago
Route Planning in Transportation Networks http://arxiv.org/abs/1504.05140 http://arxiv.org/abs/1504.05140 Shortest-Path Queries in Static Networks http://www.sommer.jp/spq-survey.pdf http://www.sommer.jp/spq-survey.pdf
nsxwolf 12y ago
As a student, this was one of the first important algorithms I ever successfully implemented in C using only a formal description of it. This and A* just make me giddy inside. The results are just magical.
waynecochran 12y ago
I wonder how many computers are running a version of Dijkstra's Algorithm as I write this? 100,000? This very post will be processed by a Dijkstra's algorithm multiple times... a truly ubiquitous algorithm...
- lucasmullens 12y ago
  When would this post be used by Dijkstra's algorithm?
kelukelugames 12y ago
This is a very dumb question. I understand how to implement Dijkstra's Algorithm. But if I want to get from point A to point B then how do I find the exact path? I have to do some processing after running the algorithm, right?
- teraflop 12y ago
  Dijkstra's has the property that it computes the cost from A to every node that is closer to A than B is. (For this reason, the distance ordering of vertices from a starting point is sometimes called their Dijkstra rank.) You can use this to backtrack and compute the actual path. Let d(x,y) be the single-edge distance between two adjacent nodes, and S(A,y) be the computed shortest path. If S(A,C) + d(C,B) == S(A,B), then any shortest path from A-C is also part of a minimal path from A-B. Starting from B, you can check all its neighbors to find one that is a predecessor on a shortest path, and then just repeat that process until you get back to the starting point. (If you look at other dynamic programming problems, like longest common subsequence, they often use similar tricks to reconstruct a solution after the initial computation is done.)
- lorenzhs 12y ago
  During relaxation (if you found a new, shorter path to a node), you don't just update the cost of getting there, but also save how you got there (i.e., from which node). Then it's just a matter of retracing the steps from B to A!
eamsen 12y ago
Nicely written article, but the writer failed to do any research on practical solutions for route planning. "The result of such an explosion is that problems, like shortest path problems, grow so quickly as to become practically incomputable, taking a practically infinite amount of time to solve." This is exactly the reason why neither Dijkstra nor a variant thereof is a feasible solution for real-world route planning (we would be talking about hours instead of ms per query). However, variants of Dijkstra are used in the pre-computational steps for the actual routing algorithms like Contraction Hierarchies or Transit Node Routing.

72 points by hemapani 12y ago

Nowerdays, Google Maps is most likely using more modern algorithms, like 'contraction hierarchies' [1] - the algorithm inserts shortcuts into the graph in a structured way, so you only switch from a higher-numbered shortcut to a lower-numbered shortcut (or non-shortcut) at the very start or end of the route. This radically reduces the number of edges that need to be explored. [1] https://www.youtube.com/watch?v=-0ErpE8tQbw https://www.youtube.com/watch?v=-0ErpE8tQbw

amelius 12y ago
A hierarchical approach makes a lot of sense, intuitively. It makes me wonder why it took so long before such method was considered.
- lorenzhs 12y ago
  The area of route planning research got a large boost with the 9th DIMACS Implementation challenge in 2005/06, this is where most of the research into fast and exact route planning algorithms started. (What sat nav vendors did and are still doing usually isn't exact, they were using inexact heuristics that were based on the 'natural' hierarchy in the road network)
lorenzhs 12y ago
Calling Contraction Hierarchies 'a variation' of Dijstra's algorithm, as the article does, is a bit of an understatement though. For anyone interested in route planning algorithms, there is a wide variety of interesting speed-up techniques. Some more key words: Arc Flags, Landmarks, Multi-Layer Dijkstra, Customizable Route Planning, Hub Labelling, Highway Hierarchies, PHAST. For transportation networks, also have a look at RAPTOR. A list of interesting references is available at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/routenplanung/index#literatur http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (the slides are in German, unfortunately)

jgrahamc 12y ago

Before there was Dijkstra's Algorithm there was still need to solve these problems. Here's a talk I gave about computing shortest paths for British Rail in 1955. https://www.youtube.com/watch?v=pcBJfkE5UwU https://www.youtube.com/watch?v=pcBJfkE5UwU

sjtrny 12y ago
You forgot the link.
- jgrahamc 12y ago
  Oops. Thanks.
elwell 12y ago
Link says talk was given in 2012 not 1955.
- IanCal 12y ago
  Assuming this is a serious comment, it's: Here's a talk I gave (about computing shortest paths for British Rail in 1955). Rather than Here's a talk I gave (about computing shortest paths for British Rail) in 1955. That is, the topic is computing shortest paths in 1955 for British Rail and the talk was given in 2012.
  - zimpenfish 12y ago
    I have to admit it gave me momentary pause for "Wow, I didn't think jgrahamc was -that- old".
    - jgrahamc 12y ago
      :-) True. 1955 < my_dob
  - elwell 12y ago
    Ha, no I was just kidding.

crypt1d 12y ago

FYI, one of the most popular routing protocols (used in internal networks) is OSPF[1], which is based on Dijkstra's algorithm. [1] http://en.wikipedia.org/wiki/Open_Shortest_Path_First http://en.wikipedia.org/wiki/Open_Shortest_Path_First

windexh8er 12y ago
When I saw the headline of the article, and being a network engineer by trade, I thought for sure this article was on OSPF. Was intrigued to see Google Maps leveraging Dijkstra's algorithm. Makes you think about traffic a bit different - I wonder if Google has the concept of backbone, stub and transit "areas" within maps? Next time I use a mapping solution I'll definitely think about it much differently, very cool. Does anyone know how costs are assigned in a mapping application that may use something like Dijkstra's? In the network world cost is derived by link speed and distance, being a general oversimplification, but I wonder how general areas are broken up into routing domains? By city or state? Very interesting...
- varjag 12y ago
  A bunch of weighing schemes possible, including speed limit, distance, congestion and toll fees. The routing algorithms for electric vehicles seem to prioritize elevation (or rather lack of) as well, to preserve battery.

tristramg 12y ago

Dijkstra’s algorithm is well known in computer science, but as other comments say it, Google uses a much more advanced algorithm. Furthermore the complexity O(n×log(n)) we know dates from the 80’s. Many years after Dijktra’s original article. I wrote a year ago a small blog post where I tried to show the chronology: http://blog.tristramg.eu/short-history-of-routes-computation.html http://blog.tristramg.eu/short-history-of-routes-computation...

farresito 12y ago
Thank you for your article. Pretty interesting. Will finish reading it when I get home.
bunderbunder 12y ago
Paraphrasing an observation that was shared with me last week, "Dijkstra was an asshole. All his stuff runs in exponential time."

deleted 12y ago

[deleted]

csom 12y ago

Route Planning in Transportation Networks http://arxiv.org/abs/1504.05140 http://arxiv.org/abs/1504.05140 Shortest-Path Queries in Static Networks http://www.sommer.jp/spq-survey.pdf http://www.sommer.jp/spq-survey.pdf

nsxwolf 12y ago

As a student, this was one of the first important algorithms I ever successfully implemented in C using only a formal description of it. This and A* just make me giddy inside. The results are just magical.

waynecochran 12y ago

I wonder how many computers are running a version of Dijkstra's Algorithm as I write this? 100,000? This very post will be processed by a Dijkstra's algorithm multiple times... a truly ubiquitous algorithm...

lucasmullens 12y ago
When would this post be used by Dijkstra's algorithm?

kelukelugames 12y ago

This is a very dumb question. I understand how to implement Dijkstra's Algorithm. But if I want to get from point A to point B then how do I find the exact path? I have to do some processing after running the algorithm, right?

teraflop 12y ago
Dijkstra's has the property that it computes the cost from A to every node that is closer to A than B is. (For this reason, the distance ordering of vertices from a starting point is sometimes called their Dijkstra rank.) You can use this to backtrack and compute the actual path. Let d(x,y) be the single-edge distance between two adjacent nodes, and S(A,y) be the computed shortest path. If S(A,C) + d(C,B) == S(A,B), then any shortest path from A-C is also part of a minimal path from A-B. Starting from B, you can check all its neighbors to find one that is a predecessor on a shortest path, and then just repeat that process until you get back to the starting point. (If you look at other dynamic programming problems, like longest common subsequence, they often use similar tricks to reconstruct a solution after the initial computation is done.)
lorenzhs 12y ago
During relaxation (if you found a new, shorter path to a node), you don't just update the cost of getting there, but also save how you got there (i.e., from which node). Then it's just a matter of retracing the steps from B to A!

eamsen 12y ago

Nicely written article, but the writer failed to do any research on practical solutions for route planning. "The result of such an explosion is that problems, like shortest path problems, grow so quickly as to become practically incomputable, taking a practically infinite amount of time to solve." This is exactly the reason why neither Dijkstra nor a variant thereof is a feasible solution for real-world route planning (we would be talking about hours instead of ms per query). However, variants of Dijkstra are used in the pre-computational steps for the actual routing algorithms like Contraction Hierarchies or Transit Node Routing.