# Contraction Hierarchies minimal distance proof

I am trying to implement "Contraction Hierarchies" algorithm and reading the white paper and watching video lectures [6,7]. But still I can't understand proof for the following lemma:

Lemma 1. $$d(s, t) = min(d(s, v) + d(v, t) : v$$ is settled in both searches $$)$$.

Proof. We only give a proof outline for self-containedness since the CH-query is a special case of the HNR-query for which a detailed yet simple correctness proof is given in [4]. In particular, here we only consider the case where shortest paths are unique.

Let $$v$$ denote the largest node on the shortest path $$P$$ from $$s$$ to $$t$$. We first claim that the sequence of prefix maxima of $$P$$ forms the shortest path from $$s$$ to $$v$$ in the upward graph $$G↑$$. If $$s = v$$ there is nothing to prove. Otherwise, consider any pair $$(u, w)$$ of subsequent prefix maxima in $$P$$ and the overlay graph $$G′ = (u..n, E′)$$ existing at some point during contraction. Since the shortest path from $$u$$ to $$w$$ uses only interior nodes smaller than $$u$$, and by definition of the properties of an overlay graph, $$(u, w) ∈ E′$$ and $$c(u, w) = d(u, w)$$. Moreover, $$u < w$$ and hence $$(u,w) ∈ G↑$$. Analogously, the sequence of suffix maxima of $$P$$ forms the shortest path from $$v$$ to $$t$$ in the downward graph.

[4] Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 66–79. Springer, Heidelberg (2007)

What I currently understood: There is a path $$P$$ from $$s$$ to $$t$$ and there is a node $$v$$ in it, with the highest importance order. The path from $$s$$ to $$v$$ consists from the prefix maxima, i.e. $$s = v_0 \to v_1 \to v_2, ... , v_k = v$$. Where $$v_i-1 < v_i$$ and $$v_{i-1} \to v_i$$ uses only nodes $$< v_{i-1}$$:

The rest of the proof is unclear. Mostly the overlay graph $$G'$$

• Can you identify the first statement in the proof that is not clear to you? – John L. Feb 12 '19 at 0:12
• 1. "consider any pair (𝑢,𝑤) of subsequent prefix maxima in 𝑃 and the overlay graph 𝐺′=(𝑢..𝑛,𝐸′) existing at some point during contraction." - Why do we need an overlay graph if we already have a shortest path from s to v ? 2. "Since the shortest path from 𝑢 to 𝑤 uses only interior nodes smaller than 𝑢, and by definition of the properties of an overlay graph, (𝑢,𝑤)∈𝐸′ and 𝑐(𝑢,𝑤)=𝑑(𝑢,𝑤)." - Well, it is clear why u to w uses only interior nodes smaller than u, but what does the next statement prove ? – maksadbek Feb 12 '19 at 7:18