Why is label pruning possible with hub labeling? Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict labels.

I don't understand how there can be labels that can be pruned. From my understanding the shortcuts added by CH should make sure that in both forward and reverse searches we will either


reach a node via a shortest path or
not reach a node at all.


How is it possible that we reach some nodes via a path that is longer than the shortest path? Could anyone provide a minimal example?
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.