<p>I have emailed the authors and they kindly supplied me with the following example:</p>

<p><img src="https://i.sstatic.net/dwGnz.png" alt="example graph"></p>

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

<p>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).</p>

<p>This means that we now have an incorrect distance label for C at A.</p>

CC BY-SA 3.0
2014-06-25T11:17:43.503Z
2014-06-25T11:17:43.503Z
Chris
<p>so that means:</p>

<p>1)
creating the forward label of A consists of yopying the upwards graph from A</p>

<p>2)
prune out all vertices from forward Label L(A) where d(s, u) > dist(s, u)
(d() = current distance; dist() = real distance; s = start-vertex; u = another vertex)</p>

<p>2.1)
do a BI-Dijsktra search from s to u and compare the calculated distance = dist(s, u) with the current distance from A's label = d(s, u)
if its greater, than prune C from A's Label L(A)</p>

<p>will this not lead to a many to many query like doing a dijsktra from almost every node to every other node?
Couldnt I then just save all results into an origin-destination matrix?
Is then the whole benefit of hub labeling just a space-better way than creating an OD-matrix?</p>

<p>Unfortunately I was not able to find a description how they do the hub labeling. They say they use the labes from CH searches. Which searches they mean? Do the really do a many to many search and then save the labes as forward and reverse?</p>

CC BY-SA 3.0
2016-01-04T11:08:52.823Z
bad question, answered in section 5.1 of HLs Paper mentioned
Kaspatoo
CC BY-SA 3.0
2016-01-04T10:57:45.710Z
2016-01-04T10:57:45.710Z
Kaspatoo
<p><a href="https://research.microsoft.com/apps/pubs/default.aspx?id=142356" rel="nofollow">Hub labeling</a> (HL) computes superlabels using the vertices visited by the forward and reverse <a href="http://algo2.iti.kit.edu/schultes/hwy/contract.pdf" rel="nofollow">Contraction Hierarchies</a> (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict labels.</p>

<p>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</p>

<ul>
<li>reach a node via a shortest path or</li>
<li>not reach a node at all.</li>
</ul>

<p>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?</p>

CC BY-SA 3.0
2014-06-03T14:53:09.910Z
I'm new to this site. Could you please let me know what the problem is when downvoting?
Chris
<ds.algorithms><shortest-path>
Why is label pruning possible with hub labeling?
Chris
# Why is label pruning possible with hub labeling?

(Asked by: username_0 on 2014-06-03)

[Hub labeling](https://research.microsoft.com/apps/pubs/default.aspx?id=142356) (HL) computes superlabels using the vertices visited by the forward and reverse [Contraction Hierarchies](http://algo2.iti.kit.edu/schultes/hwy/contract.pdf) (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?

**Tags:** ds.algorithms, shortest-path

> **Comments:**
> **username_0**: I'm new to this site. Could you please let me know what the problem is when downvoting?  

---

## 2 answers

### Answer by username_0 on 2014-06-25. Score: 3 | Accepted answer

I have emailed the authors and they kindly supplied me with the following example:

![example graph](https://i.sstatic.net/dwGnz.png)

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.


---

### Answer by username_1 on 2016-01-04. Score: -2

so that means:

1)
creating the forward label of A consists of yopying the upwards graph from A

2)
prune out all vertices from forward Label L(A) where d(s, u) > dist(s, u)
(d() = current distance; dist() = real distance; s = start-vertex; u = another vertex)

2.1)
do a BI-Dijsktra search from s to u and compare the calculated distance = dist(s, u) with the current distance from A's label = d(s, u)
if its greater, than prune C from A's Label L(A)

will this not lead to a many to many query like doing a dijsktra from almost every node to every other node?
Couldnt I then just save all results into an origin-destination matrix?
Is then the whole benefit of hub labeling just a space-better way than creating an OD-matrix?

Unfortunately I was not able to find a description how they do the hub labeling. They say they use the labes from CH searches. Which searches they mean? Do the really do a many to many search and then save the labes as forward and reverse?

> **Comments:**
> **username_1**: bad question, answered in section 5.1 of HLs Paper mentioned  

---

