# Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one)

Given a directed and strongly connected graph $G=(V,E)$, weight function $w: E \to \mathbb{R}$ and two distinct vertices $u,v \in V$. We know that there aren't negative cycles. I need to find algorithm, efficient as possible,such that for every value of $k$, $2 \leq k \leq |V|-1$, it will find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one).

I don't know what to do. I want to use Bellman Ford somehow, I just don't sure how.

Thanks a lot.

• It seems that we are spending a lot of effort doing your homework for you. What have you tried? How are you approaching the problem? Aug 28 '12 at 17:14
• This is not my home work. these are questions from past exams I'm trying to solve in order to practice myself to my exam. I don't have direction for solving the problem, as I wrote. Aug 28 '12 at 17:35

$\qquad \displaystyle \mathrm{bf}(i,j) = \begin{cases} 0 &, i = 0 \land j = s \\ \infty &, i = 0 \land j \neq s \\ \min\limits_{k \in V}\, \big(\, \mathrm{bf}(i-1,k) + c(k,j)\,\big) &, \text{else} \end{cases}$
What meaning does $\mathrm{bf}(i,j)$ have, that is what does DP-matrix entry $\mathrm{bf}[i,j]$ contain?
If you unfold the definition (i.e. proof by induction) you see that $\mathrm{bf}(i,j)$ is the weight of the shortest path from starting node $s$ to $j$ with at most $i$ edges -- exactly what you are looking for.