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.

  • 3
    $\begingroup$ 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? $\endgroup$ Aug 28, 2012 at 17:14
  • $\begingroup$ 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. $\endgroup$
    – Jozef
    Aug 28, 2012 at 17:35

1 Answer 1


Consider the dynamic programming formulation of Bellman-Ford:

$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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