0
$\begingroup$

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}$:

This drawing is from lecture slides

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

$\endgroup$
  • $\begingroup$ Can you identify the first statement in the proof that is not clear to you? $\endgroup$ – Apass.Jack Feb 12 at 0:12
  • $\begingroup$ 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 ? $\endgroup$ – maksadbek Feb 12 at 7:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.