[OSRM-talk] Questions about internals
daniel at mapbox.com
Tue Jul 12 13:00:30 UTC 2016
Yes, it's a bidirectional Dijkstra search. The Wikipedia page for CH describes it, so I won't repeat it here: https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying <https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying>
"Core nodes" are uncontracted nodes. `osrm-contract` has the option to not fully contract the edge-based graph (using the `--core` command-line parameter). In this case, the search needs to be modified when it comes across nodes that are uncontracted. The purpose of this feature is to allow faster pre-processing, at the expense of query-time performance.
If you don't use the `--core` parameter, everything gets contracted, and there are no core nodes.
> On Jul 12, 2016, at 6:51 AM, Francis Giraldeau <francis.giraldeau at gmail.com> wrote:
> I'm digging into the internals of OSRM. The Processing Flow wiki page is quite informative, here are few additional questions. I can edit the wiki with the answers.
> About the routing algorithm: when inspecting RoutingStep, there are forward and backward heap, so it looks like bidirectional Dijkstra, but the documentation states that the algorithm is based on contraction hierarchies. What's the trick?
> In the code, we see that some nodes are "core nodes". What does that mean?
> Thanks for your help!
> Francis Giraldeau
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the OSRM-talk