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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.