# Use induction to prove the correctness of shortest path algorithm

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?

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

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!