Is there an implementation of the open-source shortest-path algorithm with a distance label a la Gavoille et al.?

Question

If you are allowed to precompute the linear value in |V| data on the graph, then there is a family of algorithms that have sublinear query times for the shortest paths in the graph.

• Gavoille et al. Marking distances on graphs.
• Cohen et al. Reachability and remote requests using labels with 2 volumes
• Abraham, Goldberg et al. Hierarchical hub tags for shortest paths

Some of them are used in Bing Maps for extremely fast calculation of the shortest routes.

The basic idea is to precompute for each vertex leading labels L_f(v) and backward labels L_b(v) , which represent the coverage property. Each label represents a pair of vertices and the distance to it, for example. L_f(v) = { (u, dist(v, u)) } and L_r(v) = { (u, dist(u, v)) } . And the cover property states that for any vertices s and t L_f(s) "Union" L_r(t) contains at least one vertex on the shortest path from s to t.

Is there an open source implementation of one of these algorithms (C ++, C #, F #, D, Go, Java)?

Answer 1

I did not find the code that implements these algorithms, but you can look at the Karlsruhe homepage , where you can find the code for the Abbreviations Hierarchies, which form the basis of the (original) concentrator labeling. You can use this to create your own implementation of HL, but you should know that they have filed a patent for it.