Why is label pruning possible with hub labeling?
I have emailed the authors and they kindly supplied me with the following example:



Let the nodes be contracted in alphabetical order then the red edge will be added during contraction.

Now look at the upward search from A (i.e. we can only visit nodes that have been contracted later). A will settle B with distance 1 and D with distance 2. Since we are not allowed to visit C via D (as this is not upward) we must settle C via B with distance 6. However, as can clearly be seen from the non-contracted graph, the A-C distance is 5 (via D).

This means that we now have an incorrect distance label for C at A.