1
$\begingroup$

Suppose given a directed graph $G=(V,E)$ with positive weights and we try to find shortest path $d(s,t,\ell)$ from $s$ to $t$ such that we traverse at most $\ell$ edges ($\ell$ is even). Let $w(u,v)$ be weight of edge (u,v), so we use this recurrence, $$d(s,t,\ell)=\begin{cases} \min_{x \in V}\{d(s,x,\frac{\ell}{2})+d(x,t,\frac{\ell}{2})\},& \text{if } \ell\geq 2\\ w(s,t), & \ell=1\\ \infty, & \ell=0 \end{cases} $$

How we can prove by induction that the above recurrence find optimal solution?

I try to induction on $\ell$ so when we let $\ell=0$ the answer is $\infty$ so it's correct. Also for $\ell=1$ the correct answer is $w(s,t)$ so the recurrence is correct, but how we can extend this idea to show that whole recurrence is correct?

$\endgroup$
1
  • $\begingroup$ $\ell=1$ vs. $\ell$ is even ?!? And what if there is no single-edge path from $s$ to $t$ ?? $\endgroup$ Apr 26 at 8:16

1 Answer 1

1
$\begingroup$

Here is how a proof by induction would look like here. We prove by induction on $r$ the following claim:

For every pair of vertices $s,t$, the value of $d(s,t,2^r)$ is the length of the shortest path from $s$ to $t$ which uses at most $2^r$ edges (or $\infty$ when there is no such path).

Denote this claim by $P(r)$. You need to prove two things:

  1. Basis: $P(0)$ holds.
  2. Step: If $P(r)$ holds then $P(r+1)$ holds.

If the proof doesn't work, perhaps you need to modify your recurrence. In case this modification involves allowing lengths which are not powers of $2$, you might need to prove the following similar claim by induction on $\ell$:

For every pair of vertices $s,t$, the value of $d(s,t,\ell)$ is the length of the shortest path from $s$ to $t$ which uses at most $\ell$ edges (or $\infty$ when there is no such path).

Denoting this claim by $Q(\ell)$, the proof by induction would go as follows:

  1. Basis: $Q(0)$ and $Q(1)$ holds.
  2. Step: If $Q(r)$ holds for all $r < \ell$, then $Q(\ell)$ also holds.

Good luck!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.