14
$\begingroup$

I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to have the graph in memory, so the graph is stored on disk in a database.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

Fetching the adjacency list of each vertex visited would require about 1,500 database queries per 10,000 nodes according to my statistical data, so that clearly is not how they do it. That would be way too slow.

How do they do it? I am trying to implement it myself.

$\endgroup$
11
  • 2
    $\begingroup$ Are you sure they use Dijkstra? There are plenty of other shortest path algorithms that may be better suited to the situation you describe. $\endgroup$ Mar 26, 2016 at 16:25
  • 1
    $\begingroup$ Have you looked into the code? How should we know? "database queries" -- I hope you don't use a DBMS for storing graphs? $\endgroup$
    – Raphael
    Mar 26, 2016 at 16:39
  • $\begingroup$ @DavidRicherby yes I am sure, look at this link $\endgroup$
    – dimitris93
    Mar 26, 2016 at 16:50
  • 2
    $\begingroup$ "[I]t would be an extremely tedious process to look into pure C code." But that's the only way of knowing what the code does. So you're just asking us to do your tedious task for you, which isn't the greatest ad for your question... $\endgroup$ Mar 26, 2016 at 18:31
  • 1
    $\begingroup$ @Shiro You explicitly ask, "How do they do this?" If that's not really the question you want to ask, you need to rephrase. $\endgroup$
    – Raphael
    Mar 27, 2016 at 7:43

3 Answers 3

6
$\begingroup$

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

You can use a DB, a custom file format to be read from disc and an in-memory setting.

But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.

The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.

The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.

Regarding the other answers:

Dijkstras algorithm while applicable is regarded as not optimal for this problem

The 'normal' Dijkstra can perform very reasonable (<1s for country-wide queries like your 3mio nodes example) and is optimal in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.

road networks are hierarchical and planar.

road networks are hierarchical for car only and not planar (bridges, tunnels, ...)

$\endgroup$
21
  • $\begingroup$ I have one more question. How do you find the NodeID of the closest node from the latitude/longitude ? That is required to calculate shortest path A->B. And also we need to keep in mind that the A and B might not exist as nodes, because not every square meter contains a node. So we need to find the 2 closest NodeIDs of A and B. $\endgroup$
    – dimitris93
    Mar 29, 2016 at 17:13
  • $\begingroup$ That is done in the LocationIndexTree which is kind of a quadtree storing efficiently the NodeIDs in a cell which has e.g. for GraphHopper a radius of ~500m. If nothing is found it expands the radius up to a certain degree. This sounds simple in theory but is very complex as you might have edges crossing the area, you need to be efficient when creating and querying it and a lot more. $\endgroup$
    – Karussell
    Apr 1, 2016 at 15:50
  • $\begingroup$ Aren't KD-Trees more efficient when searching for the nearest neighbor ? Why did you chose QuadTrees over KD-Trees ? I am implementing KD-Trees for my routing engine right now. I started implementing QuadTrees but I stopped because I figured that KD-Trees is the same thing, but easier to code, and faster to query the nearest neighbor. Am I wrong ? $\endgroup$
    – dimitris93
    Apr 28, 2016 at 17:40
  • $\begingroup$ When using quadtrees there is no need to explicitely store the the bounding box giving it a storage advantage, which was more critical for my usecase (also I find quadtrees easier ;)). Query speed is not an issue. In fact someone studied such tries and it outperformed any other implementations incl. KD trees, but I assume all depends on the specific implementation... $\endgroup$
    – Karussell
    Apr 28, 2016 at 18:14
  • $\begingroup$ If you look at page 9 of this pdf from stanford, searching for nearest neighbor in KD-Trees doesn't require you to know the bounding boxes at all. And another thing is that because we know all the points beforehand, we can create a balanced tree of logn height. Are still you positive that quadtrees have any advantage over kd-trees ? $\endgroup$
    – dimitris93
    Apr 28, 2016 at 20:25
2
$\begingroup$

You do not need to put all edges that are adjacent in the priority queue. "Lie" to Dijkstra's algorithm and give it only the shortest vertex, v, incident to the vertex, say w, pulled off the stack. Then, when v is pulled of the queue you say "oops" I made a mistake and should have given you this vertex too, which is the next closest to vertex w. It is easily seen that this way you will have a correct solution and the queue size is dramatically reduced to one incident vertex only instead of the many. You need though to keep track of the incidences to always give the next closest vertex - when required. One of the comments claimed road networks are planar that is incorrect. In fact, a study has shown they are highly non-planar. Think of all motorways crossing via bridges through a city inducing many non-planarities.

$\endgroup$
0
$\begingroup$

Dijkstras algorithm while applicable is regarded as not optimal for this problem although more efficient variants could be considered as "similar". there are various simplifications. road networks are hierarchical and planar. here are the basic approaches. the area is generally known as "route planning in road networks".

  • a graph structure can be "compiled" from the adjacency list data. this is the approach in the library you cite, SpatiaLite. these graph structures are stored in a compressed binary format where graph locations are represented by binary-encoded integers etc., so the graph representation and manipulation takes much less space than storing all the road names etc.; it appears the SpatiaLite algorithm is not "online" and runs entirely in memory.

  • there are parallel/ distributed algorithms. see eg Scalable GPU Graph Traversal / Merrill, Garland, Grimshaw.

  • the question uses client-server terminology ie "queries". the algorithms do not run by "querying" the database in the client-server sense. higher level query languages such as SQL are an interface to the database and may be used to transmit the request to compute the minimal routes but are not used by the algorithm internally. generally the algorithm runs "inside the database" ie entirely "server side". so hence writing a shortest path algorithm in database queries is feasible for small networks but not medium/ large scale ones.

  • there is another approach where estimations within small percentages may be acceptable. the basic idea is to keep an index of distances between nodes. see eg Fast and Accurate Estimation of Shortest Paths in Large Graphs / Gubichev, Bedathur, Seufert, Weikum

  • this (235p!) Phd thesis is especially applicable. Route Planning in Road Networks / Schultes

  • some algorithms use many of these ideas and others, are highly tuned and proprietary and verging on competitive trade secrets. eg Google's. there may be some misleading media on this subject. eg The Simple, Elegant Algorithm That Makes Google Maps Possible which claims/ implies Google uses Dijkstras algorithm without any citation.

$\endgroup$
2
  • 1
    $\begingroup$ Google Maps certainly has upgraded to something better than Dijskstra. Every halfway competent developer would use A* for road maps, but at my previous job we found out that Google's engine could replan 2500 km routes via a waypoint in <100 ms. That's too fast for A*, so it's probable they use something like ArcFlags. $\endgroup$
    – MSalters
    Mar 30, 2016 at 9:11
  • $\begingroup$ Karussell's answer challenges this opening sentence "Dijkstras algorithm while applicable is regarded as not optimal for this problem" which did not expect would be controversial. there is very strong support for the assertion in the Schultes thesis (early on) which is also a very comprehensive/ recent survey of the area, and also explains the "hierarchical and planar" "approximations". unfortunately there seems to be no indication of the actual google algorithms in open literature on cursory search. $\endgroup$
    – vzn
    Mar 30, 2016 at 15:10

Your Answer

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

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