On Dijkstra's Algorithm | Hacker News Reader

On Dijkstra's Algorithm

motherboard.vice.com

72 pointshemapani26 comments

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...

Thank you for your article. Pretty interesting. Will finish reading it when I get home.

Paraphrasing an observation that was shared with me last week, "Dijkstra was an asshole. All his stuff runs in exponential time."

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

You forgot the link.

Oops. Thanks.

Link says talk was given in 2012 not 1955.

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.

I have to admit it gave me momentary pause for "Wow, I didn't think jgrahamc was -that- old".

:-) True. 1955 < my_dob

Ha, no I was just kidding.

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

A hierarchical approach makes a lot of sense, intuitively. It makes me wonder why it took so long before such method was considered.

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)

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/route... (the slides are in German, unfortunately)

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

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...

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.

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.

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.

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?

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.)

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!

Route Planning in Transportation Networks http://arxiv.org/abs/1504.05140

Shortest-Path Queries in Static Networks http://www.sommer.jp/spq-survey.pdf

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...

When would this post be used by Dijkstra's algorithm?

Reply on news.ycombinator.com